TL;DR
- A Vision Transformer's attention has no built-in notion of which patches are neighbors; only the positional embeddings carry that. Large models trained on large datasets learn locality anyway, but small models and small datasets suffer.
- VIOLIN borrows the decay mask from linear transformers: each attention score is multiplied, before the softmax, by γd, where d is the distance between the two patches along a scan of the image.
- A single scan order distorts 2D distance, so VIOLIN uses eight space-filling curves (Snake, Zig-zag, Hilbert and Peano, each with a transposed copy) and averages their masks. It adds 1,296 parameters to DeiT-B, 0.0015% of the model.
- Added at fine-tuning time, it raises VTAB-1K accuracy on all nine backbones tested, by up to 8.7 points on the Structured tasks that depend on spatial layout. In pretraining it adds 0.8 and 0.9 points on ImageNet for DeiT-T and DeiT-S, and 7.2 points for a DeiT-T trained on individual pixels of CIFAR-100.
Attention does not know which patches are neighbors
A ViT cuts the image into patches, flattens them into a sequence and runs self-attention over it. Attention is permutation equivariant: shuffle the patches and the outputs shuffle the same way. Nothing in the attention itself says that two patches are adjacent; that information comes only from the positional embeddings, and the model has to learn to use it.
CNNs get locality for free from their small kernels. With enough parameters and data a ViT learns it too, but for small models (the paper uses 30M parameters or fewer as the cut-off) or small datasets it does not learn it well. Fine-tuning a large pretrained ViT on a thousand examples is the second case.
A decay mask from linear transformers
Linear transformers such as RetNet order tokens with a decay factor γ instead of position embeddings: token i sees token j with weight γi-j. Written as a full, non-causal matrix this is the Kac-Murdock-Szegő mask, and VIOLIN multiplies it into the attention scores:
Distant pairs have their scores shrunk toward zero, so only nearby pairs can keep large scores. The mask does not block attention; it is a soft prior, much like the distance penalty in ALiBi but multiplied into the scores instead of added to them.
The distance |i - j| is measured in the flattened sequence, so it depends on how the image was flattened. Row-major order, which the paper calls the Z-curve and which most ViTs use, keeps horizontal neighbors one step apart but puts vertical neighbors a full row apart. It also places the last patch of one row right next to the first patch of the next, although they sit on opposite edges of the image.
Eight curves instead of one
A space-filling curve visits every cell of a grid exactly once. The paper uses four, each defined in its Appendix B.3 and code:
- Snake: row by row, reversing direction on every other row, so the end of one row is next to the start of the next.
- Zig-zag: along the anti-diagonals, alternating direction, the order JPEG uses for DCT coefficients.
- Hilbert: the recursive quadrant curve, built with the same generalized Hilbert ("gilbert") algorithm as the Hilbert-Guided Sparse Local Attention paper.
- Peano: the paper's name for the Morton or Z-order curve, which sorts patches by interleaving the bits of their row and column. It is a different curve from the row-major "Z-curve" above.
Each curve also has a transposed copy that swaps rows and columns, Fc^\top(i, j) = Fc(j, i), giving eight curves in all.
Running attention once per curve would multiply the cost by eight. Instead, VIOLIN computes Q, K and V once in row-major order and moves each curve's mask into that order with a permutation, \widetilde{M}c = Pc^\top Mc Pc. One QK^\top then serves every curve:
Each curve's decay is learned per head as γc = \text{sigmoid}(βc), and each head also learns the scale α. That is L · h · (|𝒞c| + 1) parameters: 12 · 12 · 9 = 1{,}296 for DeiT-B, 0.0015% of its 86M, and 0.64% more FLOPs.
Why average the curves
Every curve fails somewhere. The table below uses the demo's model on a 14×14 patch grid with γ = 0.9 and lists, over every reference patch, the weakest weight any curve gives to a patch that shares an edge with the reference, and the strongest weight it gives to a patch at least four steps away. These are this page's own calculations, not numbers from the paper.
| Mask | Weakest edge neighbor | Strongest patch 4+ steps away |
|---|---|---|
| Row-major | 0.229 | 0.900 |
| Snake | 0.058 | 0.656 |
| Zig-zag | 0.065 | 0.810 |
| Hilbert | 8×10⁻⁸ | 0.656 |
| Peano | 6×10⁻⁴ | 0.900 |
| VIOLIN average | 0.239 | 0.516 |
Hilbert keeps patches inside a quadrant close, but two patches on either side of a quadrant boundary can end up more than 150 steps apart. Row-major and Peano both place some patches that are far apart in the image right next to each other in the sequence. The average cannot fall that far: every horizontal neighbor is adjacent on the Snake curve and every vertical neighbor on the transposed Snake, so each edge neighbor keeps at least γ / 8. The paper's Claim C.4 states the general version: no single curve moves the average by more than 1/m for m curves, and if a fraction p of the curves place two patches within r steps, the averaged mask is at least pγr.
The pretraining ablation (Table 12, DeiT-S on ImageNet, baseline 79.9%) points the same way. Peano alone gives the largest single-curve gain (+0.5), Hilbert alone gives none, and all four together give +0.8.
The learned decays tend to stay close to 1 (the paper's Figure 5). On 196 patches even γ = 0.9 gives a patch at the far end of the sequence, 195 steps away, a weight of 0.9195 ≈ 10-9, so values near 1 are what keep long-range attention alive. A curve whose γc drops low contributes little to the average, which lets each head and layer favor particular curves.
Results
Fine-tuning on VTAB-1K (Table 3). VTAB-1K has 19 tasks with 1,000 training examples each, in three groups: Natural, Specialized and Structured. VIOLIN's mask is added to a pretrained model, freshly initialized, and fine-tuned together with it. Accuracy is the average over all three groups.
| Model | Params | Baseline | With VIOLIN | Structured group |
|---|---|---|---|---|
| DeiT-T | 5M | 65.52% | 68.33% (+2.81) | +3.93 |
| DeiT-S | 22M | 67.38% | 70.46% (+3.08) | +4.82 |
| DeiT-B | 86M | 70.35% | 72.95% (+2.60) | +4.89 |
| DeiT-III-S | 22M | 67.57% | 72.31% (+4.74) | +8.69 |
| DeiT-III-B | 86M | 70.63% | 73.94% (+3.31) | +6.32 |
| DeiT-III-L | 304M | 67.41% | 69.51% (+2.10) | +3.55 |
| DeiT-III-H | 632M | 66.91% | 68.50% (+1.41) | +2.95 |
| DINO-S | 22M | 71.21% | 71.84% (+0.63) | +0.59 |
| DINO-B | 86M | 71.23% | 72.79% (+1.56) | +2.37 |
The Structured group (counting objects, locating them, estimating depth and orientation) gains the most, which is what a spatial prior should help. The mask also combines with parameter-efficient fine-tuning on DeiT-B: LoRA goes from 71.04% to 72.55% and DoRA from 70.75% to 71.90%. Masks learned only during fine-tuning beat masks carried over from VIOLIN pretraining (Appendix F.2).
Pretraining (Tables 5, 6 and 17). On ImageNet-1K with the DeiT recipe, DeiT-T goes from 72.2% to 73.0% and DeiT-S from 79.8% to 80.7%. Self-supervised DINO-S improves by 0.3 to 0.7 points in k-NN and linear evaluation. At base size the gain nearly disappears: DeiT-B goes from 81.8% to 81.9%. Training a DeiT-T on individual pixels of CIFAR-100, where no patching supplies any locality, the mask lifts accuracy from 60.8% to 68.0%.
Dense prediction (Table 7). Semantic segmentation on ADE20K with DeiT-B and UPerNet improves from 45.24 to 45.80 mIoU. Detection on COCO with a Swin-T backbone and Mask R-CNN moves from 42.7 to 42.8 box AP and from 39.3 to 39.7 mask AP.
Other locality priors (Table 8). All methods start from the same pretrained DeiT-B and are fine-tuned on the Structured group, where the baseline scores 57.00%.
| Method | Extra parameters | Structured average |
|---|---|---|
| VIOLIN | ~1.3K | 61.89% |
| Single curve (Peano) | ~0.4K | 61.63% |
| Swin relative position bias | ~105K | 61.58% |
| LocalViT | ~6.2M | 61.50% |
| iRPE on Q, K and V | ~115K | 61.45% |
| VIOLIN mask added, not multiplied | ~1.3K | 61.34% |
| Manhattan-distance mask | ~0.4K | 58.37% |
VIOLIN scores highest, with about a thousand parameters against 105K for Swin's relative position bias and 6.2M for LocalViT. Multiplying the mask into the scores beats adding it, and a mask built from plain 2D Manhattan distance gains far less than any curve-based mask.
Critical analysis
Strengths:
- Cheap and drop-in. About a thousand parameters and no change to the rest of the network. It can be bolted onto any pretrained global-attention ViT at fine-tuning time, alongside LoRA or DoRA.
- Helps where it should. The largest gains are on the Structured tasks and on pixel-level CIFAR-100, the two settings that depend most on spatial layout.
- A clear reason to average. Claim C.4 and the curve ablation both say the same thing: each curve distorts 2D distance in its own way, and the average is more robust than any one of them.
Limitations:
- Gains shrink with scale. ImageNet pretraining gains fall from +0.9 points on DeiT-S to +0.1 on DeiT-B, and VTAB gains from +4.74 on DeiT-III-S to +1.41 on DeiT-III-H. The paper says as much: the method targets small models and small datasets.
- Much of the gain comes from having any decay mask. In the DeiT-S pretraining ablation (Table 13, baseline 79.8%), a mask from row-major order alone gives +0.7 points against +0.9 for all eight curves. On the Structured group a single Peano curve gets within 0.26 points of the full set.
- Not free at runtime. The mask adds 0.64% FLOPs, but DeiT-S inference with a batch of 256 goes from 206.1 to 233.1 ms per batch at 224×224, about 13% slower, and from 1739.3 to 1789.7 ms (about 3%) at 512×512 (Table 2). Memory is essentially unchanged.
- It keeps global attention's cost. The mask is a dense N × N multiply, so attention stays quadratic. The Hilbert-Guided Sparse Local Attention paper uses the same curve for the opposite purpose: to make local attention fast rather than global attention more local.
- Small gains on dense prediction. The improvements are +0.56 mIoU on ADE20K and +0.1 box AP on COCO.
Related Reading
- Hilbert-Guided Sparse Local Attention: the same generalized Hilbert curve, used to make local attention block-sparse and fast
- Vision Transformer (ViT): the global-attention ViT whose missing locality VIOLIN adds back
- DINO: the self-supervised ViT that VIOLIN improves in both pretraining and fine-tuning
- LoRA: the parameter-efficient fine-tuning method VIOLIN combines with on VTAB-1K
- Swin Transformer: whose relative position bias is one of the locality priors VIOLIN is compared against