{"id":"dbd8850f-2388-406d-924f-e92d91023d9c","arxiv_id":"2507.02957","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"CSAT applies compressed sensing ideas to Transformer attention by projecting keys and values into low dimensions and decoding outputs with learned sparse recovery, claiming linear complexity with benchmark performance near full attention.","lead":"This paper proposes CSAT, an attention mechanism for vision-language transformers that compresses keys and values with random projections and reconstructs outputs with sparse-coding decoders like LISTA. The authors claim linear-time attention with accuracy matching full attention, but the theoretical guarantee rests on an unproven equivalence and the experiments omit code, hyperparameters, and error bars.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The CSAT recovery guarantee does not follow from the paper's own computation: Z_i is a softmax-weighted, data-dependent projection of V, not a fixed RIP measurement of the sparse context vector, and the claimed equation Z_i = ΦΨα_i has mismatched dimensions.","rationale":"The reader's weakest_assumption identifies the same load-bearing weakness: the recovery equation assumes Z_i is a fixed linear function of the sparse context vector, but the paper's own definition makes Z_i depend nonlinearly on Q and K through the softmax. Reading Section 3 in good faith, the intended contribution is a theoretically grounded efficient attention mechanism where attention outputs are recovered from compressed measurements under RIP. For that claim to be true, the map from α_i to Z_i would have to be a fixed measurement matrix; the equations show it is not, and additionally the dimensions of Φ_V and Z_i are incompatible with the written recovery model. The empirical results are also underspecified, but the theoretical gap is more decisive and independently sufficient to block the central claim. The paper's Limitations section concedes that sparsity may not hold broadly and that decoding can be a bottleneck, but those are secondary; the primary issue is that the formal guarantee does not apply to the proposed computation. I therefore agree with the REJECT verdict and recommend no change.","tokens_in":10969,"tokens_out":3449,"duration_ms":37971,"concrete_test":"Fix small dimensions, e.g., n=16, d_k=8, m=4. Choose a random dictionary Ψ and a sparse coefficient vector α_i, define C_i = Ψα_i. For random Q, K, V and random RIP-style Φ_K, Φ_V, compute the actual row Z_i = [softmax(Q(Φ_K K)^T / √d_k) Φ_V V]_i. Then compare Z_i against Φ_V C_i and against Φ_V Ψα_i, computing normalized ℓ2 errors over many draws. Separately, run basis pursuit or LISTA to recover α_i from Z_i and report success rate for small sparsity levels. If Z_i does not equal the proposed measurement model, or if recovery fails even though C_i is sparse, the claimed RIP-based guarantee is not the operative mechanism.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that CSAT recovers sparse context vectors under RIP fails because the equation Z_i = ΦΨα_i does not describe the operation actually computed in Section 3. The paper defines K̃ = Φ_K K, Ṽ = Φ_V V, then computes Z = softmax(Q K̃^T / √d_k) Ṽ. Each row is therefore Z_i = softmax(Q Φ_K^T K^T / √d_k)_i · Φ_V V, a nonlinear function of Q, K, and V. It is not a fixed linear measurement Φ_V C_i of the true context C_i = softmax(Q K^T / √d_k) V: projecting the keys before softmax changes the attention weights, and multiplying Φ_V V by the compressed attention row is not equivalent to applying Φ_V after full attention. There is also a dimensional inconsistency: Φ_V ∈ R^{m×n}, while Z_i ∈ R^{d_k}, so Φ_V Ψ α_i (length m) cannot equal Z_i (length d_k) as written. Consequently, the basis-pursuit/RIP recovery guarantee is not established for the actual mechanism. Even granting sparsity of C_i in Ψ, the measurement map from α_i to Z_i depends on the data through Q and K, and the paper provides no argument that this map is fixed, incoherent, or RIP-compliant. This gap is load-bearing because the paper's claimed novelty is precisely the formal CS connection; without it, CSAT reduces to an underspecified linear-attention variant with no recovery guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Compressed Sensing Attention Transformer (CSAT), an attention mechanism that compresses the key and value matrices with random measurement matrices, computes attention scores in the compressed space, and reconstructs attention context vectors via sparse recovery (ISTA or LISTA). The authors claim a complexity reduction from O(n^2 d) to O(n m d + decoding) and assert a formal connection to compressed sensing through the Restricted Isometry Property (RIP), arguing that attention context vectors are sparse and recoverable from the compressed outputs. The experimental section reports results on WikiText-103 language modeling, LRA Pathfinder-X, and vision-language benchmarks (Flickr30k, MS-COCO), claiming competitive or slightly better performance than full attention and linear-attention baselines. The paper's novelty rests on the theoretical recovery guarantee and the modular sparse-decoder design.","tokens_in":11312,"tokens_out":4740,"duration_ms":49745,"significance":"If the theoretical claim were correct, the paper would introduce a principled, theoretically grounded efficient attention mechanism for vision-language models, which is a timely and valuable goal. The idea of treating attention context vectors as sparse signals and using CS-style decoding is creative, and the modular decoder (analytical vs. learned) is a practically appealing design choice. However, the central derivation is invalid: the quantity actually computed by CSAT is not a fixed linear measurement of a sparse context vector, and the main equation exhibits a dimensional mismatch. In addition, the empirical evaluation is too underspecified—no hyperparameters, no seeds, no error bars—to verify the reported results or the claimed efficiency-accuracy trade-off. The core contribution is therefore not established, and the manuscript cannot be accepted in its current form.","major_comments":[{"comment":"The identity Z_i = ΦΨα_i does not describe the operation actually computed by the architecture. From the definitions in Section 3, Z_i = softmax(Q Φ_K^T K^T / √d_k)_i · Φ_V V, which is a nonlinear, data-dependent function of Q, K, and V. It is not a fixed linear measurement Φ_V C_i of the true context C_i = softmax(QK^T/√d_k)V, because projecting the keys before softmax changes the attention weights, and because the compressed attention row multiplies Φ_V V rather than V. Consequently, the basis-pursuit recovery guarantee with a fixed, RIP-compliant measurement matrix does not apply to CSAT as defined, and the central theoretical claim in Section 5 is unsubstantiated.","section":"Section 3, Eqs. (4)-(6)"},{"comment":"The claimed equation Z_i = ΦΨα_i is dimensionally inconsistent. With Φ_V ∈ R^{m×n}, Ψ ∈ R^{d_k×d_k}, and α_i ∈ R^{d_k}, the product Φ_V Ψ α_i has length m, whereas Z_i is a row of the compressed attention output and therefore has length d_k. A measurement matrix for a d_k-dimensional context vector would need to act on the feature dimension (i.e., lie in R^{m×d_k}), but the paper reuses Φ_V, which acts on the token dimension. This conflates the sequence-length and feature-embedding spaces and makes the recovery problem as formulated ill-posed.","section":"Section 3, Eq. (6)"},{"comment":"The claimed complexity of O(n m d + decoding) is incomplete. The decoding step is applied row-wise to Z ∈ R^{n×d_k}; for ISTA/LISTA, the per-row cost involves matrix-vector multiplications with the learned matrices S and B and depends on the number of unrolled iterations t. The paper does not specify the shapes of S and B, the value of t, or the cost per iteration, so the claimed linear scaling in n is not established. The efficiency comparison in Table 5 cannot be interpreted without a concrete complexity analysis of the decoder.","section":"Section 3 and Eq. (9)"},{"comment":"The experimental results are reported as single point estimates with no standard deviations, number of seeds, or training details. The CSAT-specific hyperparameters m (measurement dimension), s (sparsity), and t (decoder depth) are never stated, and the vision-language experiments do not specify how the baselines were trained or fine-tuned (e.g., learning rate, batch size, number of steps, and whether the same budget was used for all methods). This makes the reported results irreproducible and the claimed efficiency-accuracy trade-off unverifiable.","section":"Section 4, Tables 1-4"}],"minor_comments":[{"comment":"The title refers to 'CS-VLM' while the architecture is called 'CSAT' throughout the text; please reconcile the nomenclature.","section":"Title/Abstract vs. body"},{"comment":"Reference [6] and reference [22] are the same paper (Papyan et al., 2020); remove the duplicate.","section":"References"},{"comment":"The dimensions of the LISTA matrices S and B are not defined; specify their shapes in terms of m, d_k, and the decoder depth t.","section":"Section 3, Eq. (9)"},{"comment":"Report the hardware, batch size, and measurement methodology used for the runtime and GPU memory numbers.","section":"Table 5"},{"comment":"The conclusion claims 'state-of-the-art or competitive performance,' but the results in Tables 1-4 are at best competitive with baselines; soften this claim to match the reported evidence.","section":"Conclusion"},{"comment":"The limitations section acknowledges that the sparsity assumption may break down, but it does not address the more fundamental issue that the formal recovery guarantee is derived for a quantity that is not actually computed; please add a discussion of this gap.","section":"Section 7"}],"recommendation":"reject","confidential_remarks":"The central theoretical claim of the paper is not merely unpolished but incorrect: the architecture computes a nonlinear, data-dependent projection, not a fixed linear measurement, and the key equation is dimensionally inconsistent. This is a load-bearing error that invalidates the paper's main novelty. The empirical section, while suggestive, lacks the detail needed for verification. The manuscript would require a substantially different theoretical framing and much more thorough experimentation to be considered further; I do not see a feasible revision within the current scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper proposes a plausible-sounding marriage of compressed sensing and linear attention, but its central theoretical claim is not valid as written, and the experiments don't fill the gap. Still, it is not a waste of time—it is a well-written, honestly limited attempt at a real problem, and the flaws are instructive.\n\nWhat is actually new: the specific combination of random measurement matrices on keys/values with a LISTA-style sparse decoder for attention is not in the cited literature, and the benchmark numbers are new. The paper also deserves credit for framing attention as sparse recovery, acknowledging in its own Limitations section that the sparsity assumption may not generalize and that decoding can bottleneck.\n\nWhere it falls apart: the RIP-based recovery guarantee does not follow from the mechanism described. In Section 3, the compressed output is Z_i = softmax(Q Φ_K^T K^T / √d_k)_i · Φ_V V. That is a data-dependent, softmax-weighted projection of V, not a fixed linear measurement of the true context vector C_i. Choosing Φ = Φ_V and writing Z_i = ΦΨα_i does not hold either dimensionally (Φ_V is m×n, Z_i is d_k) or structurally: softmax is nonlinear and the effective measurement map depends on Q and K. No argument shows this map is incoherent or RIP-compliant. This is the load-bearing contribution, so without it the method is just an underspecified linear-attention variant with no recovery guarantee.\n\nThe experiments are also underreported: no hyperparameters, no seeds, no error bars, no code. Tables 3 and 4 show CSAT beating the full-attention BLIP baseline on retrieval and captioning, which strains credibility for a compressed approximation—that alone warrants scrutiny.\n\nWho this is for: readers working on efficient attention who want to see how compressed sensing ideas can get misapplied. It could spark a useful reading-group discussion about why the softmax breaks the linear measurement assumption.\n\nRecommendation: it deserves a serious referee rather than a desk reject, because the direction is worth exploring and the mistakes are identifiable and potentially fixable. But the current version should be rejected. If the authors can either make the recovery guarantee honestly apply to the actual computation or drop the CS pretense and present CSAT as a heuristic linear-attention variant, there may be a viable paper underneath.","headline":"The recovery guarantee doesn't survive contact with the actual computation, but the paper is a clear, motivated attempt worth engaging with.","tokens_in":11832,"tokens_out":2003,"would_cite":false,"duration_ms":24844,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that attention outputs are sparse enough to be compressed by random projections and reconstructed by sparse recovery, cutting vision-language attention from quadratic to linear cost.","keywords":["compressed sensing attention","sparse recovery","vision-language transformers","linear attention","Restricted Isometry Property","cross-modal retrieval","image captioning","long-sequence modeling"],"falsifier":"Measure the decoder's reconstruction error $\\|\\hat{C}_i - C_i\\|_2$ on tokens whose attention weights are nearly uniform over many keys; if that error rises sharply as attention entropy increases, the sparsity premise on which CSAT's guarantee rests is refuted.","tokens_in":10736,"feed_emoji":"⚡","tokens_out":11436,"duration_ms":107076,"temperature":0.7,"pith_summary":"The paper sets out to show that attention in vision-language transformers does not need to be computed over all token pairs. Its central proposal, CSAT, compresses keys and values with random measurement matrices, computes attention in the compressed space, and reconstructs the original context vectors by sparse recovery. If this works, the quadratic $O(n^2 d)$ cost of attention drops to $O(n m d + \\text{decoding})$ with $m \\ll n$, which would let vision-language models process longer video and text sequences. The paper reports that this compressed model matches or slightly beats full attention and linear-attention baselines on language modeling, long-range classification, image-text retrieval, and captioning. It also claims to be the first to tie attention-output structure to sparse-signal recovery under the Restricted Isometry Property.","feed_headline":"Compressed-sensing attention cuts quadratic cost to linear","feed_subtitle":"CSAT projects keys and values into few measurements, then rebuilds attention via sparse recovery, matching full-attention benchmarks.","key_machinery":"The load-bearing object is a pair of random measurement matrices $\\Phi_K, \\Phi_V \\in \\mathbb{R}^{m \\times n}$ that project the key and value matrices into $m \\ll n$ dimensions before attention, together with a sparse decoder that recovers each context row from $Z_i = \\Phi\\Psi\\alpha_i$ by $\\ell^1$-minimization, approximated by ISTA or its learned unrolled form LISTA. The Restricted Isometry Property (RIP) is the condition the paper invokes to guarantee that the sparse coefficients $\\alpha_i$ can be stably recovered; the complexity saving comes from computing attention scores against the $m$-dimensional compressed keys instead of all $n$ tokens.","core_discovery":"The central claim is that each attention context row $C_i$ is sparse or compressible in a dictionary $\\Psi$, so that after compressing keys and values with random measurement matrices, the observed compressed row $Z_i$ is a valid compressed-sensing measurement $Z_i = \\Phi\\Psi\\alpha_i$. The model then solves for $\\alpha_i$ by $\\ell^1$-minimization (basis pursuit) using ISTA or its learned unrolled form LISTA and reconstructs the context as $\\hat{C}_i = \\Psi\\hat{\\alpha}_i$. The paper asserts that this is the first formal link between attention-output structure and sparse-signal recovery under the Restricted Isometry Property, and that in practice the compressed model matches or exceeds full attention and linear-attention baselines on WikiText-103, LRA Pathfinder-X, Flickr30k retrieval, and MS-COCO captioning.","pith_inferences":["Editorial extension: the paper's own Section 7 concedes that dense-attention tasks may break the sparsity premise; a concrete test is whether CSAT's advantage shrinks on fine-grained video captioning or crowded-scene detection.","Editorial extension: the implemented measurement path includes a data-dependent softmax, so a fully rigorous version of the theory would need to fix or bound that nonlinearity; without that, the RIP guarantee is a formal analogy rather than a theorem about the trained model.","Editorial extension: if the sparsity premise holds, the decoder coefficients double as a per-token measure of information loss, so the measurement count $m$ could be chosen adaptively during inference, a use the paper leaves implicit.","Editorial extension: when the learned LISTA decoder replaces exact recovery, the theoretical guarantee degrades to the approximation quality of the unrolled network; measuring how many unrolled iterations match exact basis pursuit would quantify the trade-off."],"forward_implications":["Vision-language attention can scale linearly with sequence length without assuming the attention matrix is low-rank, because the saving comes from computing scores against $m \\ll n$ compressed keys.","CSAT blocks can replace individual attention heads or layers in a pretrained model, giving incremental efficiency gains without retraining from scratch.","The sparse decoder's coefficients provide an interpretability map showing which compressed visual and textual components drive each reconstructed context vector.","For video and long-form inputs, where temporal and spatial redundancy is high, the efficiency gains of compressed attention should be largest."],"supporting_citations":[{"why":"Supplies the compressed-sensing recovery theory that CSAT's sparsity premise builds on.","marker":"[8]"},{"why":"Establishes RIP-based guarantees for exact sparse recovery, the theoretical backing CSAT invokes.","marker":"[25]"},{"why":"Defines the low-rank linear-attention baseline CSAT is compared against and distinguished from.","marker":"[33]"},{"why":"Provides the random-feature kernel approximation baseline used in benchmark comparisons.","marker":"[34]"},{"why":"Supplies the LISTA unrolled decoder used to approximate sparse recovery inside the network.","marker":"[37]"},{"why":"Defines the basis-pursuit $\\ell^1$ problem that the formal recovery step solves.","marker":"[26]"},{"why":"BLIP is the vision-language backbone into which CSAT is integrated and against which it is benchmarked.","marker":"[28]"},{"why":"Empirical evidence that deep features concentrate along low-dimensional structures, supporting the compressibility assumption.","marker":"[22]"},{"why":"Shows cross-modal attention concentrates on few tokens, the empirical basis of the sparsity premise.","marker":"[30]"}],"fun_headline_variants":["Compressed sensing attention: linear cost, full fidelity","CSAT: Sparse recovery for attention in vision-language models","Quadratic attention slashed to linear via compressed sensing","Vision-language attention rebuilt via compressed sensing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recovery guarantee assumes the compressed attention row is exactly a fixed random measurement matrix applied to a sparse code, but the row the network actually computes goes through a data-dependent softmax, so the fixed-measurement assumption is not established.","fun_headline_variants_meta":{"raw":{"variants":["Compressed sensing attention: linear cost, full fidelity","CSAT: Sparse recovery for attention in vision-language models","Quadratic attention slashed to linear via compressed sensing","Vision-language attention rebuilt via compressed sensing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1536,"prompt_tokens":992,"completion_tokens":544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":608,"completion_tokens_details":{"reasoning_tokens":482}},"tokens_in":608,"tokens_out":544,"duration_ms":6699,"temperature":1.0,"reasoning_tokens":482,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:41:21.034123+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the decoder's reconstruction error $\\|\\hat{C}_i - C_i\\|_2$ on tokens whose attention weights are nearly uniform over many keys; if that error rises sharply as attention entropy increases, the sparsity premise on which CSAT's guarantee rests is refuted.","supporting_citations":[{"cited_title":"Compressed sensing","cited_arxiv_id":null,"evidence_quote":"Supplies the compressed-sensing recovery theory that CSAT's sparsity premise builds on."},{"cited_title":"Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information","cited_arxiv_id":null,"evidence_quote":"Establishes RIP-based guarantees for exact sparse recovery, the theoretical backing CSAT invokes."},{"cited_title":"Rethinking attention with performers","cited_arxiv_id":null,"evidence_quote":"Provides the random-feature kernel approximation baseline used in benchmark comparisons."},{"cited_title":"Learning fast approximations of sparse coding","cited_arxiv_id":null,"evidence_quote":"Supplies the LISTA unrolled decoder used to approximate sparse recovery inside the network."},{"cited_title":"S., Donoho, D","cited_arxiv_id":null,"evidence_quote":"Defines the basis-pursuit $\\ell^1$ problem that the formal recovery step solves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"BLIP is the vision-language backbone into which CSAT is integrated and against which it is benchmarked."},{"cited_title":"Y., and Donoho, D","cited_arxiv_id":null,"evidence_quote":"Empirical evidence that deep features concentrate along low-dimensional structures, supporting the compressibility assumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows cross-modal attention concentrates on few tokens, the empirical basis of the sparsity premise."}],"review_version":1}