{"id":"246806d3-8754-4e75-bd9c-a07dd52266e0","arxiv_id":"2505.16463","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A vision transformer reduces self-attention complexity from O(n^2) to O(mn) by using m learnable anchor tokens and a two-step Markov transition between anchors and tokens.","lead":"AnchorFormer replaces the quadratic self-attention of vision transformers with a linear-complexity anchor attention, where a few learnable anchor tokens summarize the image. The authors report substantial FLOPs savings and accuracy gains on three vision benchmarks, making the paper relevant to anyone building efficient transformers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (8) assumes anchors are a sufficient statistic for global attention; without an error bound or a Nyströmformer/Perceiver comparison, Eq. (11)'s claim to approximate global self-attention is unsupported, leaving the O(mn) method's central promise resting on uncontrolled downstream numbers.","rationale":"The reader's CONDITIONAL verdict is appropriate. I considered a stronger objection—that Eq. (4)'s p(u_j|v_i)=p(v_i|u_j) is mathematically false and undermines the Markov derivation. This is real but not fatal: replacing the false equality with the correct column normalization Δ^{-1}A^T still yields the same final formula, so the algebra of Eq. (11) survives. The deeper issue is Eq. (8)'s sufficiency assumption, which is precisely the reader's weakest_assumption. I therefore agree with the reader's diagnosis. The paper deserves credit for the correct rearrangement in Eq. (12) and for the explicit low-rank factorization, but the absence of both an error bound and comparisons to the closest existing methods leaves the central claim conditional. My proposed check can settle whether the approximation error is actually small and whether the mechanism outperforms a generic low-rank baseline; absent that, the unexplained 9.0% accuracy and 45.75 mAP numbers are not sufficient evidence that AnchorFormer's Markov framing adds value over Nyström-style attention. The verdict should remain CONDITIONAL; no change is required.","tokens_in":14236,"tokens_out":7300,"duration_ms":65851,"concrete_test":"Take a trained AnchorFormer with m=30 anchors and, on ImageNet validation, compute at each layer the full attention output H_full = softmax(QK^T/√d)V and the anchor output H_anchor = AΔ^{-1}A^T V, reporting the mean relative Frobenius error ||H_full−H_anchor||_F/||H_full||_F across layers. Train an identically sized Nyströmformer (and, if feasible, Perceiver-style cross-attention) with the same m and training budget. If the relative error is large (>0.5) or the Nyströmformer matches AnchorFormer's top-1 accuracy at equal FLOPs, the distinctive 'Markov/global-attention approximation' claim is unsupported and the reported gains are not attributable to the proposed mechanism. If the error is small and AnchorFormer clearly outperforms the low-rank baseline, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"AnchorFormer's central claim is that Eq. (11), H = AΔ^{-1}A^T V, computes a faithful approximation of global self-attention at O(mn) cost. The matrix algebra leading to Eq. (11) is internally consistent: F^2 in Eq. (9) is a valid two-step transition over the token-anchor bipartite graph. The load-bearing step is Eq. (8), p(v_j|v_i)=Σ_l p(v_j|u_l)p(u_l|v_i), which asserts that an intermediate anchor u_l renders token-to-token attention conditionally independent. That is exactly a rank-m/Nyström bottleneck; it does not follow from the softmax in Eq. (2) or from any data property, and no bound on ||AΔ^{-1}A^T V − softmax(QK^T/√d)V|| is given. For arbitrary attention matrices the relative error can be O(1), so the claim that global similarities are 'accurately' learned is not established. The conceptual problem is compounded by Eq. (4)'s assertion p(u_j|v_i)=p(v_i|u_j); conditional probabilities are not symmetric, and only the explicit Δ normalization makes the final formula a row-stochastic matrix. Thus the Markov-process rhetoric overstates what is a standard low-rank approximation. Because Table 1's 9.0% improvement and Table 2's 45.75 mAP are not accompanied by comparisons to Nyströmformer/Perceiver or PP-PicoDet, the empirical evidence does not currently separate the anchor approximation from a generic learned low-rank attention. This is not a rejection of the method; low-rank attention can be effective. It is a statement that the central claim's key condition—that m anchors faithfully capture global attention—is assumed, not demonstrated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces AnchorFormer, a vision transformer variant that replaces global self-attention with an anchor-based attention computed as H = A Δ^{-1} A^T V (Eq. 11), where A is an n×m token-anchor attention matrix. The complexity is reduced from O(n^2) to O(mn) by reordering multiplications as B^T V → Δ^{-1}(B^T V) → B(Δ^{-1}B^T V). Anchors are represented as learnable neurons in a neural layer, making the selection differentiable. The authors evaluate AnchorFormer on ImageNet classification, COCO detection, and ADE20K segmentation, reporting accuracy/flops trade-offs that are often better than the listed baselines. The paper also claims that the Markov process derivation justifies that Eq. (11) accurately approximates global self-attention.","tokens_in":14599,"tokens_out":5256,"duration_ms":41981,"significance":"If the method delivers the reported trade-offs, it would be a practically useful efficient attention module, particularly for high-resolution vision tasks. The differentiable anchor formulation and the O(mn) complexity are appealing, and the ablation study (§4.6) shows that the differentiable anchor mechanism contributes substantially to the gains. However, the central theoretical claim—that Eq. (11) 'accurately' approximates global self-attention via a Markov process—is not supported by the derivation, which is a low-rank (Nyström-style) bottleneck rather than an exact reduction. The empirical sections are extensive but do not include comparisons to established linear/low-rank attention methods, and some headline numbers in the abstract are computed under non-comparable FLOPs budgets. The significance is therefore conditional on reframing the contribution as a learned low-rank attention with strong empirical results, rather than as a proved approximation of global attention.","major_comments":[{"comment":"The derivation of Eq. (11) relies on the assumption p(v_j|v_i) = Σ_l p(v_j|u_l)p(u_l|v_i), i.e., that the anchor u_l makes token pairs conditionally independent. This is a modeling choice, not a consequence of the softmax in Eq. (2) or of any data property. No bound is provided for ||A Δ^{-1} A^T V − softmax(QK^T/√d)V||, and for arbitrary attention matrices the relative error can be O(1). The paper should either supply such a bound or explicitly state that AnchorFormer is a learned low-rank approximation of attention, not an 'accurate' global self-attention as claimed in the abstract and Section 3.2.","section":"§3.2, Eq. (8)–(11)"},{"comment":"The headline gains are not consistently computed under comparable conditions. The abstract's '81.3% higher mAP' corresponds to comparing AnchorFormer-B (2.8 GFLOPs) with YOLOX-Nano (0.54 GFLOPs), which are not comparable FLOPs; under comparable FLOPs, e.g., EfficientDet-512 at 2.5 GFLOPs versus AnchorFormer-B, the gain is about 35%. Similarly, the '9.0% higher accuracy' appears to come from the apple-to-apple DeiT replacement in Fig. 5a, not from the cross-architecture comparisons in Table 1. The authors should state the exact comparison pairs and compute percentage gains under matched FLOPs budgets.","section":"Abstract and §4.3–4.4"},{"comment":"The text states 'BiFormer-B takes 15.5G FLOPs to achieve 84.42% accuracy', but Table 1 lists BiFormer-B at 9.8 GFLOPs. The claimed FLOPs reduction of 40.6% for AnchorFormer-B versus BiFormer-B is therefore incorrect; the actual reduction is about 6.1% (9.2 vs. 9.8 GFLOPs). This quantitative claim needs to be corrected, and the comparison should be re-evaluated accordingly.","section":"§4.3, Table 1"},{"comment":"The empirical evaluation does not include established linear/low-rank attention methods such as Nyströmformer, Perceiver, or Linformer. Since Eq. (11) is structurally a low-rank approximation, comparisons to these methods are needed to determine whether the anchor mechanism offers advantages over a generic learnable low-rank projection, or whether the reported gains are due to other components of the architecture. Without such baselines, the claim of superiority over 'current baselines' is overstated.","section":"§4.3–4.5, Tables 1–3"}],"minor_comments":[{"comment":"The softmax indices appear to be transposed: in vanilla self-attention one normally has p(v_j|v_i) = exp(q_i k_j^T / √d) / Σ_j exp(q_i k_j^T / √d). Please clarify the notation.","section":"§3.2, Eq. (2)"},{"comment":"The sentence 'where m is the number of tokens' should read 'where m is the number of anchors'.","section":"§3, first paragraph"},{"comment":"The equality p(u_j|v_i) = p(v_i|u_j) is not generally true for conditional probabilities. While the algebra leading to Eq. (11) uses the row-stochastic matrices rather than this equality, the statement is misleading and should be rephrased or removed.","section":"§3.2, Eq. (4)"},{"comment":"The closed-form expression for u treats p(u|v_i) as a constant when differentiating the objective in Eq. (3), but p(u|v_i) depends on u through Eq. (4). This is acceptable as a motivation, but the paper should note that Eq. (5) is only an approximate stationary point, since the actual anchors are learned via gradient descent.","section":"§3.2, Eq. (5)"},{"comment":"The table caption and the text say 'DeiT-T and DeiT-T are employed', but the rows clearly refer to DeiT-T and DeiT-S. Please correct the caption.","section":"§4.6, Table 5"},{"comment":"The dataset is referred to as 'ADE210K'; the correct name is ADE20K.","section":"§4.5, Table 3"},{"comment":"The references [61]–[66] on positive-incentive noise appear unrelated to the main contribution of this paper; if they are not directly used in the argument, please remove them or integrate them into the related work with a clear connection.","section":"§5, Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The empirical results are potentially interesting, but the current framing overclaims both the theoretical justification and the numerical comparisons. The absence of comparisons to Nyströmformer/Perceiver and the miscalculated FLOPs reduction in Table 1 should be addressed before publication. I would also encourage the editor to verify the baseline numbers against the original sources, as some comparisons in Tables 1–2 seem to mix different training settings."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the core formula is a known low-rank Nyström-style approximation of attention, and the reported gains are too large to accept without code and training details. That said, the method is coherent, the anchor-as-neurons trick is a neat implementation choice, and the ablations on anchor count are useful. The paper is not a hoax; it is an over-framed re-packaging of landmark-based attention.\n\nThe algebra in Section 3.2 works out. With A row-stochastic and Δ the diagonal of column sums, S_t = AΔ^{-1}A^T is a two-step transition on the token-anchor graph, and S_t 1_n = 1_n holds. The complexity reduction is real. But the Markov-process story overreaches. Eq. (4) asserts p(u_j|v_i)=p(v_i|u_j), which is not true because the two conditional distributions have different normalizations; the Δ^{-1} in Eq. (11) only fixes row-stochasticity, not the equality. Eq. (8) is the real assumption: that anchors are a sufficient statistic for token-to-token attention. No error bound is given, and without one there is no reason to believe S_t is close to softmax attention. This is exactly the Nyström approximation from Nyströmformer and Perceiver, which the paper never cites. That is a significant missing baseline, both in the round and in the experiments.\n\nThe experimental section is the softest part. An 86.62% top-1 at 9.2 GFLOPs and 45.75 mAP at 2.8 GFLOPs are far above the listed baselines. The paper does not compare to Nyströmformer, Perceiver, or PP-PicoDet, and it does not report training epochs, augmentations, or other recipe details. The abstract's 9.0% accuracy and 81.3% mAP improvements are relative numbers that look cherry-picked. The ablations on anchor number are the one part of the experiments that is clearly informative.\n\nThere is also a citation-padding smell in the conclusion, where a series of self-citations on 'positive-incentive noise' appears with no connection to the method. Minor, but it does not build confidence.\n\nWho is this for? Someone interested in efficient vision transformers might take the anchor-as-neurons idea as a useful implementation note, but they would already know the underlying approximation. For me, this is a revise-and-resubmit candidate only if the authors add the missing comparisons, disclose training details, release code, and stop claiming the method is new. It deserves a referee because the empirical claims, if reproducible, would matter. I would not cite it in my own work in the meantime.","headline":"Known Nyström-style low-rank attention, re-packaged as a Markov process, with implausibly large accuracy gains and no code or closest-baseline comparisons.","tokens_in":15203,"tokens_out":6990,"would_cite":false,"duration_ms":57541,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"AnchorFormer shows that a vision transformer can keep global self-attention while cutting compute from quadratic to near-linear in the number of image patches, by routing attention through a small set of differentiable anchor tokens.","keywords":["vision transformer","efficient attention","anchor tokens","bipartite attention","Markov process","linear complexity","image classification","semantic segmentation"],"falsifier":"Take images where informative content is spread across the whole frame, such as dense small-object scenes, and compare a trained AnchorFormer against the same model with full softmax attention: if the gap between $A\\Delta^{-1}A^T$ and the exact attention matrix is large while accuracy holds, the approximation's sufficiency would be questioned; if accuracy drops sharply whenever the exact attention matrix has high rank, the linear-complexity claim would be refuted for those inputs.","tokens_in":14030,"feed_emoji":"⚡","tokens_out":11507,"duration_ms":80182,"temperature":0.7,"pith_summary":"AnchorFormer is a vision transformer designed to keep the global attention of a standard ViT while escaping its quadratic cost. The idea is to route attention through a small set of $m$ anchor tokens: build a bipartite attention matrix between tokens and anchors, then reconstruct the full token-to-token attention as the one-step Markov transition through the anchors. The resulting attention $H = A\\Delta^{-1}A^T V$ is never materialized as an $n \\times n$ matrix; rearranging the multiplication order brings complexity from $\\mathcal{O}(n^2)$ to $\\mathcal{O}(mn)$. The authors report 86.62% top-1 accuracy on ImageNet at 9.2 GFLOPs and 45.75 mAP on COCO at 2.8 GFLOPs, alongside improvements on semantic segmentation. If correct, this gives a drop-in attention module that scales to high-resolution images and small patch sizes without giving up a global receptive field.","feed_headline":"Anchor set replaces quadratic attention with near-linear cost","feed_subtitle":"On ImageNet it reaches 86.62% top-1 at 9.2 GFLOPs; on COCO, 45.75 mAP at 2.8 GFLOPs.","key_machinery":"The central object is the differentiable anchor-attention block: a small set of anchor tokens, implemented as neuron weights, that act as a learned bottleneck for global attention. It computes a bipartite token-anchor attention matrix $A$, builds the Markov transition matrix $F = D^{-1}G$ on the token-anchor graph, and reads off the approximate global attention $S_t = A\\Delta^{-1}A^T$ from $F^2$. The identity carrying the argument is $H = A\\Delta^{-1}A^T V$, evaluated as $A(\\Delta^{-1}(A^T V))$ so that complexity stays at $\\mathcal{O}(mn)$ instead of $\\mathcal{O}(n^2)$. The Markov property supplies the probabilistic interpretation: $p(v_j|v_i) = \\sum_{l=1}^m p(v_j|u_l)p(u_l|v_i)$, meaning the anchors summarize the full attention distribution.","core_discovery":"AnchorFormer's central claim is that global self-attention can be approximated accurately by a two-step path through $m$ learnable anchors: tokens attend to anchors, and anchors attend back to tokens. Writing $A \\in \\mathbb{R}^{n \\times m}$ for the token-anchor attention matrix and $\\Delta$ for the diagonal matrix of anchor degrees, the approximate token-to-token attention is $S_t = A\\Delta^{-1}A^T$, normalized so its rows sum to one, and the output is $H = A\\Delta^{-1}A^T V$. The anchors are represented as rows of a learnable weight matrix in a neural layer, so they are fitted by gradient descent rather than chosen by a separate non-differentiable selection step. Evaluating the product as $A(\\Delta^{-1}(A^T V))$ avoids ever forming an $n \\times n$ matrix, giving $\\mathcal{O}(mn)$ complexity. The paper reports that this construction matches or surpasses efficient-attention baselines on classification, detection, and segmentation while cutting FLOPs.","pith_inferences":["Editorial inference: since $A\\Delta^{-1}A^T$ has rank at most $m$, the approximation's ceiling is the effective rank of the true attention matrix; measuring that rank on real images would predict where the anchor bottleneck starts to hurt.","Editorial inference: the paper states AnchorFormer is incompatible with causal attention, but a masked variant of $A$ that forbids future tokens would likely restore causality at the same $\\mathcal{O}(mn)$ cost, opening an unstated path to language-model use.","Editorial inference: the paper's own framing of anchor attention as a noisy approximation suggests deliberately calibrating that noise, and a testable extension would compare deterministic anchors against anchors trained to inject controlled beneficial noise."],"forward_implications":["Global self-attention can be computed in $\\mathcal{O}(mn)$ without forming an explicit $n \\times n$ attention matrix, so ViTs can be applied to higher-resolution images or smaller patch sizes at roughly linear cost in the number of patches.","Because the anchors are learned by gradient descent, the model concentrates computation on informative regions without a separate region-selection step, which the paper argues is why it outperforms sparse-attention baselines such as PVT.","The approximation can be dropped into existing backbones: the paper demonstrates gains on DeiT and LeViT for ImageNet classification, on ESNet for COCO detection, and on Semantic-FPN and UperNet for ADE20K segmentation.","Anchor count is a real hyperparameter with a sweet spot near 30 anchors; too few anchors discard features, while too many add redundant information, according to the ablations.","The construction is independent per attention head, so the efficiency gain carries over to multi-head self-attention and hence to whole transformer stacks."],"supporting_citations":[{"why":"Supplies the softmax self-attention formulation and the $\\mathcal{O}(n^2)$ cost that AnchorFormer approximates.","marker":"[1]"},{"why":"Defines patch-based vision transformer processing that AnchorFormer inherits.","marker":"[2]"},{"why":"Provides the shifted-window attention baseline that AnchorFormer compares against on ImageNet and segmentation.","marker":"[3]"},{"why":"Is the bi-level routing attention baseline that AnchorFormer claims to beat at lower FLOPs.","marker":"[9]"},{"why":"Is the sparse-attention baseline whose hand-selected regions AnchorFormer argues can discard informative features.","marker":"[10]"},{"why":"Supplies the anchor and bipartite-graph mechanism that the Markov transition and complexity reduction are built on.","marker":"[12]"},{"why":"Provides the DeiT backbone and training setup used for the ImageNet classification comparisons.","marker":"[37]"},{"why":"Provides the ESNet backbone whose last stage AnchorFormer replaces for the COCO detection experiments.","marker":"[55]"}],"fun_headline_variants":["AnchorFormer: differentiable anchors turn attention near-linear","Learnable anchor tokens speed up ViT attention to O(mn)","Anchor attention: efficient ViT with learned anchors","Near-linear self-attention via learned anchors in ViT","AnchorFormer: anchor-based attention drops quadratic cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a small set of anchor tokens is a sufficient summary of the global attention distribution, so the one-step Markov transition through the anchors loses no information the downstream task needs; the paper assumes this rather than proving it and gives no error bound for the approximation.","fun_headline_variants_meta":{"raw":{"variants":["AnchorFormer: differentiable anchors turn attention near-linear","Learnable anchor tokens speed up ViT attention to O(mn)","Anchor attention: efficient ViT with learned anchors","Near-linear self-attention via learned anchors in ViT","AnchorFormer: anchor-based attention drops quadratic cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00032,"raw_usage":{"total_tokens":1859,"prompt_tokens":1058,"completion_tokens":801,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":724}},"tokens_in":674,"tokens_out":801,"duration_ms":5984,"temperature":1.0,"reasoning_tokens":724,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:00:22.258533+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take images where informative content is spread across the whole frame, such as dense small-object scenes, and compare a trained AnchorFormer against the same model with full softmax attention: if the gap between $A\\Delta^{-1}A^T$ and the exact attention matrix is large while accuracy holds, the approximation's sufficiency would be questioned; if accuracy drops sharply whenever the exact attention matrix has high rank, the linear-complexity claim would be refuted for those inputs.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the shifted-window attention baseline that AnchorFormer compares against on ImageNet and segmentation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the bi-level routing attention baseline that AnchorFormer claims to beat at lower FLOPs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the sparse-attention baseline whose hand-selected regions AnchorFormer argues can discard informative features."},{"cited_title":"Touvron, M","cited_arxiv_id":null,"evidence_quote":"Provides the DeiT backbone and training setup used for the ImageNet classification comparisons."}],"review_version":1}