Autoregressive image generators produce a picture one small patch, or "token," at a time, and each new token looks back at all earlier ones through attention. The model learns how much weight to give each earlier token. Most such models generate in raster order, row by row from the top left, and the methods that speed them up by forgetting part of that history are built around this order. They always keep the first few rows, treated as a global summary, and the most recent tokens, treated as local neighbours. Those methods sometimes even improve image quality, because discarding irrelevant distant tokens removes background noise from the attention. Random-order generators such as RandAR train one model to produce tokens in any order and tell it where each token goes. In those models "first" and "recent" no longer mean "global" and "nearby," so the existing forgetting rules stop making sense. The obvious fix is to replace chronology with 2D coordinates. That fix is easy, so it is not enough to justify a project.
The more interesting observation is that a random-order model lets us choose the generation order itself. We can therefore pick an order that makes aggressive forgetting safe by construction. The model first generates a small, evenly spread "anchor" set of tokens that covers the whole canvas like a coarse sketch. Every later token then attends only to those anchors plus its spatial neighbours, selected by coordinate distance. The method needs no retraining and never reads attention scores to decide what to drop. We hypothesise that this does more than save memory. RandAR's reported loss of fine detail when it extrapolates from 256 to 512 pixels may be caused partly by attention spreading thin over hundreds of distant, weakly related tokens. If so, coordinate filtering combined with an anchor-first order should recover that detail.
Core Claim
The claim is that, in order-agnostic visual autoregression, the generation order and the attention filter should be designed together. The scheme is a coverage-guaranteeing anchor phase followed by coordinate-local infill with a fixed anchor budget. We expect it to match dense attention at 256×256 with a large reduction in the stored history of earlier tokens' attention keys and values (the "KV cache"). We also expect it to beat dense attention at 512×512 extrapolation, because the noise-filtering effect grows with context length.
The closest work comes from two lines that never meet. The first line is raster-bound cache filters, which motivate the design but cannot transfer to random orders:
- SparseAR uses next-token entropy to decide whether to keep the full cache, only the prefix plus recent tokens, or a top-K selection.
- ADSA keeps a 5% prefix and a local window, filters the rest by similarity of their value vectors, and slightly improves FID.
- SSD splits attention heads into spatial-locality heads and semantic-sink heads, with the image's margin columns acting as anchors.
All three treat sequence position as a stand-in for spatial role.
The second line breaks raster order but keeps dense attention:
- RandAR inserts a position instruction token, encoded with 2D rotary embeddings, before each patch. It trains on uniformly random permutations and supplies the model we build on.
- LPD schedules parallel decoding groups by their proximity to already-generated context. This is the nearest precedent for a designed order, but its attention over history stays dense.
Our proposal differs from LPD by using the order to justify sparsity rather than parallelism. It differs from the cache filters by keying retention on coordinates and coverage rather than chronology.
One point in the research file needs correcting. The file argues that the first 5% of tokens in a random order are "randomly scattered" and therefore useless as anchors. A uniformly random 5% of positions is in fact a rough, unstratified sketch of the whole image. This sharpens the question rather than removing it: chronological early tokens under a random order may already be decent anchors. Whether deliberate even coverage helps beyond that is an empirical question our ablations isolate.
Research Program
Stage 1: measure attention in a random-order model. This is diagnostic and fills an open question raised by SSD and by work showing that order-agnostic objectives change how attention is allocated (reversal-curse analysis of masked diffusion). For RandAR under random-order decoding at 256 and at extrapolated 512 resolution, we record three quantities for each layer and head:
- the fraction of attention mass as a function of 2D grid distance;
- the fraction landing on chronologically early tokens versus spatially even ones;
- attention entropy as generation progresses.
The aim is to learn whether spatial-locality heads and sink-like heads still appear without scanlines, and what serves as the sink. Candidates are the first tokens generated, class or prompt tokens, or particular positions. The aim is also to test whether the long tail of attention mass on distant tokens grows at 512, which is what the attention-noise explanation predicts.
Stage 2: the anchor-first order. Generation proceeds in two phases.
- Anchor phase. First generate an anchor set $\mathcal{A}$ of $m$ positions chosen for even coverage, using a stratified grid jitter or blue-noise sample, with dense attention among the anchors.
- Infill phase. Generate the remaining positions in random order or in a locality-friendly order. Each infill token at coordinate $p$ attends only to $\mathcal{A} \cup \{j : \lVert p_j - p \rVert_\infty \le r\}$, meaning the anchors plus already-generated tokens within a square neighbourhood of radius $r$.
Because RandAR is trained on all orders, the anchor order is within its training distribution. The cache cost per step is bounded by $m + (2r+1)^2$ regardless of image size, which is where the gains at higher resolution would come from.
We will vary $m$ and $r$, and test a per-head variant in which heads that Stage 1 identifies as long-range keep full anchors plus a wider radius.
Stage 3: a cheap correction for the softmax normalisation. Dropping tokens changes the softmax normaliser, the shift that Re-ttention corrects in diffusion transformers. Its correction relies on caching ratios across repeated denoising steps, which causal decoding does not have. We will therefore test whether a single per-head temperature, calibrated offline on dense-attention runs, closes any gap. We treat this as an ablation, not a core contribution.
Baselines
Dense RandAR (the do-nothing reference). Dense RandAR in its standard random order is the reference point. The file reports FID 2.15 for RandAR-XXL on ImageNet 256×256 (RandAR). For 512×512 extrapolation the file contains no reported result on Lacuna, so we will measure dense RandAR ourselves with the same sampling settings. Matching 2.15 within noise while storing a fraction of the cache counts as success at 256. A lower FID than dense attention at 512 is the decisive positive result.
Chronological filter transplanted from the raster methods. This is the strongest existing approach: the ADSA/SparseAR rule applied unchanged to RandAR under random order. We keep the first 5% of generated tokens plus the most recent window, and for the SparseAR version use entropy-gated top-K. On raster LlamaGen, ADSA reports FID 2.58 against 2.62 for full context. This rule is the incumbent recipe, and the file predicts it will fail on random orders by evicting true neighbours. We run it at the same cache budget, the same RandAR checkpoint and the same samples. Beating it means lower FID at equal memory, and a widening gap as the cache budget shrinks.
Coordinate filter with random-order anchors (key ablation). This baseline uses our coordinate window but takes the chronologically first $m$ tokens of a plain random order as anchors, with no designed coverage. It isolates whether choosing the order matters. If it ties our method, the contribution reduces to coordinate keying plus the Stage 1 analysis, and we will report that.
LPD-style dense decoding. LPD-XL is reported at FID 2.10 in 20 steps (LPD). It shows what a well-designed order achieves with dense history. We compare memory and FID at matched step counts where the codebase allows, and use ARPG as a second randomised-parallel model to check that our results are not specific to RandAR.
Why not just…?
Why not just use a fixed 2D local window? ADSA reports that window-only attention causes semantic drift, producing repeated textures and broken layout because no token sees the whole canvas. Our $m=0$ setting reproduces exactly this baseline, so the experiment measures directly how much the anchors buy.
Why not just keep the first tokens of an ordinary random order as anchors? This is the most serious threat. As argued above, a random prefix already roughly covers the image. The coordinate-filter-with-random-anchors ablation settles the question. We expect designed coverage to matter most at small $m$, where random samples leave holes, and at 512, where holes grow. If the prediction fails, we drop the claim that the order must be designed.
Why not just select history by attention score, as H2O or top-K query selection do? Score-based selection does not depend on chronology, so it is a fair order-agnostic competitor. SparseAR and SSD report that H2O and StreamingLLM degrade sharply on raster image models. Those results come from raster models, though, and random order could change them. We run H2O-style heavy-hitter retention at equal budget. It also needs attention scores to be computed before pruning, so we report both quality and wall-clock time.
Why not just fine-tune RandAR with sparse attention masks? Fine-tuning could beat any training-free method. We include a short fine-tune with our masks as an upper bound, using a fixed and reported compute budget. The training-free variant is useful if it comes close to that bound. If fine-tuning dominates by a large margin, we will say so.
Proposed Experiments
Main setting. The experiments use class-conditional ImageNet at 256×256 and RandAR's 256→512 extrapolation. We report FID, peak KV memory, and latency at batch sizes 1 and 32. Batch 32 is included because LPD finds that query overhead shifts parallel decoders from memory-bound to compute-bound above batch 16.
Zero-shot editing. We repeat the comparison for zero-shot inpainting and outpainting, where the known pixels are placed in the anchor set. This tests whether the conditioning region can serve as the anchors.
Text-to-image check (secondary). If a random-order text-to-image checkpoint is available, we use GenEval to test prompt adherence. SparseAR's claim that filtering sharpens prompt focus would predict a gain there.
Decisive checks.
- Does attention noise explain the 512 failure? The Stage 1 long tail of attention mass on distant tokens should grow from 256 to 512. Coordinate filtering at 512 should reduce FID relative to dense attention.
- Does the order matter? Designed-coverage anchors should beat random-prefix anchors at equal $m$, with the gap shrinking as $m$ grows.
- Does the incumbent fail as predicted? The transplanted chronological filter should degrade faster than ours as the budget tightens.
Each check can fail independently, and each failure would narrow the claim in a specific, reportable way.
References
- Entropy-Aware Dynamic KV Cache Sparsification for Autoregressive Image Generation and Editing
- Make It Efficient: Dynamic Sparse Attention for Autoregressive Image Generation
- SSD: Spatial-Semantic Head Decoupling for Efficient Autoregressive Image Generation
- RandAR: Decoder-only Autoregressive Visual Generation in Random Orders
- Locality-aware Parallel Decoding for Efficient Autoregressive Image Generation
- Understanding the Reversal Curse Mitigation in Masked Diffusion Models through Attention and Training Dynamics
- Re-ttention: Ultra Sparse Visual Generation via Attention Statistical Reshape