Optimizing Attention

There are severe methodological issues with this paper.

At a high level, if the motivation in the introduction for the work is the reduce the memory requirements for running a transformer by eliminating the Q and K matrices, in an effort to have less cache thrashing on edge devices (lines 032-035), then the experimental section needs to provide data on how the proposed intervention improves on this aspect. I would expect to see strong baselines against FlashAttention(1-3) in particular, as they're methods to run an arbitrary transformer without modification. To this effect, it appears as though only Table 1 is comparing against baseline methods.

Table 1 - What is immediately obvious is that the DETR baseline is superior at every average precision level. The key difference, I suppose is that it has Q and K projection matrices, which this paper wants to eliminate. Presumably, the next set of baselines are DETR, but with identity mappings instead of QK projections. I would have liked to see this choice motivated by latency/throughput analysis on the target device. The expectation would be that it's much faster (due to claimed reduction of cache requirement), but also noticeably worse (this table). Regardless, the only place where the proposed method seems to be consistently better is with decoder cross attention, as the two self-attention rows seem to be worse than the baseline. The discussion on lines 254-257 "This shows that it is indeed possible to replace the standard attention mechanism with our proposed optimization-based approach while maintaining model performance." is not consistent with the caption in Table 1 "It can be seen that the proposed algorithm achieves superior results." which makes it unclear what is being compared. Aside from conjecture, the paper doesn't demonstrate that it is faster, or even necessarily that it's theoretically faster, on device.

"At the same time, our proposed approach does not require softmax and is by design parallelizable." - This would be an excellent opportunity to demonstrate how this actually affects latency/throughput on modern hardware.

Equation 6 - Given that $\nu$ is a reduction operation, are we comparing the computation expense of $\alpha(x) = x^5$ versus $e^x$ as in softmax?

General methodology issues:

• There are 4 usages of "We notice", but none of them seem to be accompanied by empirical or theoretical evidence.
• It would good to see comparisons with similar-in-class methods. Given DeTr's age (4 years), certainly there have been subsequent works. Do any of those also address edge device efficiency? If so, they need to make it into Table 1.

1. The proposed method introduces new hyperparameters, such as the lambda in Equation 3 and the number of random tokens for regularization. These hyperparameters are not automatically optimized and may require tedious manual tuning.
2. The experimental setup has several issues:
   a. The choice to use DETR without weights as a baseline seems questionable. The paper critiques attention for its large matrices in mapping inputs to queries, keys, and values. Therefore, a comparison with the original DETR, including its performance, would be more appropriate than comparing it to variants without weights.
   b. The paper overlooks important efficiency metrics, such as latency, model size, and memory consumption.
   c. An experiment fully replacing both self-attention (SA) and cross-attention (CA) with the proposed attention mechanism is missing. This would better demonstrate the method's effectiveness in replacing traditional attention mechanisms.
   d. The paper should consider comparisons with additional baselines, such as simple pooling techniques, as explored in PoolFormer.
   e. Evaluating only on detection tasks is insufficient. Including experiments on other modalities and tasks, such as text processing, which depends more heavily on long-range context modeling, would strengthen the paper.

I have several concerns regarding the proposed approach:

1. Computational Complexity: The proposed method involves computationally expensive operations, such as singular value decomposition (SVD) and matrix inversion, which raises concerns about the scalability of the model for large-scale training. I would encourage the authors to provide a detailed complexity analysis comparing their approach to standard attention mechanisms, especially with regard to the SVD and matrix inversion operations. Additionally, runtime comparisons on larger datasets would help to clarify the implications of these operations for scalability.
2. Evaluation Limited to Computer Vision: The experimental evaluation focuses solely on computer vision datasets, raising concerns about the method's generalizability to other domains, such as natural language processing (NLP). Given the widespread use of transformers in NLP tasks, I recommend that the authors expand their evaluation to include popular NLP benchmarks such as machine translation (e.g., WMT), text classification (e.g., GLUE), or question answering (e.g., SQuAD). This would provide a more comprehensive assessment of the method’s versatility across different applications.
3. Manuscript Clarity and Structure: The paper would benefit from more thorough polish and a clearer exposition of certain sections. For instance, the explanation of the proposed optimization approach could be more detailed, particularly in how the random token augmentation and the efficient updates interact with the ADMM framework. Moreover, the experimental section could be expanded to discuss the results more comprehensively, including potential limitations and future work. Rather than suggesting a strict target page count, I recommend focusing on clarifying and expanding specific sections that currently feel underdeveloped or rushed.

Lastly, I would gently suggest that the authors aim for a manuscript of approximately 10 pages. The current version appears rushed and would benefit from more thorough polish.

Line 142: The statement is not clear. "These messages are sum-aggregated before the nodes in the query set are updated by an MLP". How did MLP come in the explanation of self-attention operation between query and value. The results are only done for the tast of object detection. In otder to better evaluate the performance of this new optimization stretegy, the results of other tasks such as image classification, segmentation etc should be shown. In Table 1 most of the comparative results with baselines shows that this method is inferior to baselines. Even though the proposed method talks about the efficiency due to not storing attention matrices, it does not shows any efficiency metric such as latency, FLOPs, parameter count, peak memory etc. The results shown in qualitative part is inconclusive.