We thank the reviewers for their constructive feedback and ideas. We are happy that the reviewers like the elegant and insightful framework (BdYW) that is grounded in both theoretical insight and empirical validation (pbyL), its effectiveness (BdYW,YchT) and novelty (BdYW,mHJ9,pbyL,YchT), and the clear and well-structured description (mHJ9,pbyL). The provided feedback helps us to improve the paper and we will address the individual concerns raised by reviewer YchT below.

Efficiency: Although the operations seem simple, I would still like to know whether computing the TokenRank vector will have a cost in efficiency. I wonder how many iterations are needed on average to compute the steady state vector and how much time will they cost. When TokenRank is used in downstream tasks like zero-shot segmentation and unconditional image generation with SAG, how much time is added when using TokenRank?

TokenRank converges typically within 20 iterations for SD1.5. The $\lambda_2$ value can directly indicate how many iterations will be needed, though computing $\lambda_2$ currently takes more time than computing TokenRank. As for computation, we profiled SAG and it takes roughly 1.2x times to perform with TokenRank (averaged over thousands of samples). This relatively mild extra computational effort is because it involves a very efficient (vector,matrix) product operation, which is performed on the GPU. We implemented a batched version as well. For zero-shot segmentation, it takes 1.1x more times to perform 2 bounces compared with the baseline with 1 bounce (e.g. column- select.

It would be nice if we can see the application of TokenRank on natural language processing

Thanks for this comment. Similarly to our response to reviewer BdYW, while we appreciate the impact of our study might have been stronger by validating and experimentation with other modalities, we intentionally focused on extensive and rigorous experimentation on one specific domain for the purpose of anchoring this interpretation as useful and impactful. We consider exploring the usefulness of our framework for other domains such as NLP, motion or video would be an exciting future work prospect.

Exploration of TokenRank with multi-modal cross attention: I think this work itself is rather complete. Potential directions to explore would be seeing whether the representation generated by TokenRank can locate specific objects in local regions, instead of a global representation of the image presented in this work.

This is a great direction. While TokenRank is by nature a global indicator, we presented multi-bounce as its “counter-part” that allows for local probing. One interesting way of fully exploiting the Markov chain formulation and “localizing” TokenRank, is to introduce the famous “personalization” vector from Google’s PageRank paper. This vector was originally designed to allow ranking pages of the internet but take into account user preferences (e.g. if a user like sports -> rank sports related pages higher). In our case, such a vector could potentially be used to “personalize” TokenRank, such that specific semantic tokens / groups of tokens are ranked higher (e.g. “cat” related tokens). We have not validated this approach, but believe it could be used to solve more elaborate and localized downstream tasks.

We thank the reviewers for their constructive feedback and ideas. We are happy that the reviewers like the elegant and insightful framework (BdYW) that is grounded in both theoretical insight and empirical validation (pbyL), its effectiveness (BdYW,YchT) and novelty (BdYW,mHJ9,pbyL,YchT), and the clear and well-structured description (mHJ9,pbyL). The provided feedback helps us to improve the paper and we will address the individual concerns raised by reviewer mHJ9 below.

In Section 4.1, the authors describe existing interpretations of attention mechanisms. However, I find this description to be incomplete, as it does not mention [1], which merges attention maps using KL divergence. Moreover, the comparative experiments do not include a comparison with this method.

We thank the reviewer for this reference. While this method does not provide any new interpretation of the attention maps per se (KL-divergence is used to measure similarity between upsampled attention maps), we agree it solves the same downstream task with partially similar toolkits (self-attention matrices, treating rows as probability distributions, aggregation of heads, etc.). We therefore evaluate [1] on our benchmark and found that our work outperforms [1] significantly:

For [1], mAP cannot be computed since the method does not provide raw scores.

Note: we acquired class-specific semantic segmentation labels from the predicted labels using the Hungarian algorithm, following the original author's implementation.

Additionally, inspired by the reviewer’s comment and in line with our goal of demonstrating the versatility of our framework, we incorporated TokenRank into the framework of [1]. Specifically, instead of sampling anchors from a uniform grid as in the original study the authors used a uniform grid to initialize the anchors used as seeds for their proposal algorithm. Instead, we sample anchors according to their TokenRank importance, with suppression to avoid repeatedly selecting the same location. This “smart” grid strategy leads to substantial improvements over the original approach, as demonstrated on COCO-Stuff-27 benchmark from [1]:

This new experiment further strengthens our study by demonstrating the versatility of our framework. This experiment also shows our framework is orthogonal to other solutions leveraging self-attention for solving downstream tasks. We once again would like to thank the reviewer for introducing us to this study.

We will include the results in the updated manuscript.

The experimental results shown in Figure 6 of the supplementary material are convincing. However, I hope the authors can provide some visualizations of the feature maps or attention maps to further enhance the credibility of their results.

Thank you for the suggestion. While we did include additional visualizations in the supplementary (Fig. 7 for semantic segmentation and Fig. 8 for TokenRank), we will add further examples including more visualizations of the bouncing operation across different initial states, models, images, layers, and heads, as well as additional semantic segmentation examples.

it would be necessary to include more qualitative results directly in Figure 3. Moreover, the comparative methods included in the supplementary material appear to be insufficient.

We will add more qualitative results including comparisons to recent methods in Figure 3 and more results in the supplementary.

In Figure 5, the authors demonstrate the effectiveness of the SAD method on the SD1.5 architecture. However, since SD1.5 is based on a UNet architecture, it would be valuable to include qualitative results on methods utilizing DiT-based architectures, such as PixArt or Flux.

We agree that applying our approach to DiT-based architectures would strengthen the work. However, SAG was specifically designed and thoroughly tested for Stable Diffusion and is not readily compatible with models like PixArt, and certainly not FLUX (due to the lack of an unconditional branch). Our SAG experiment serves as a representative use case, demonstrating that TokenRank captures global importance more effectively than the column sum operation in a generative downstream task. We will mention the other models in the discussion.

We thank the reviewers for their constructive feedback and ideas. We are happy that the reviewers like the elegant and insightful framework (BdYW) that is grounded in both theoretical insight and empirical validation (pbyL), its effectiveness (BdYW,YchT) and novelty (BdYW,mHJ9,pbyL,YchT), and the clear and well-structured description (mHJ9,pbyL). The provided feedback helps us to improve the paper and we will address the individual concerns raised by reviewer pbyL below.

L7-8: "set of metastable states where the attention clusters while noisy attention scores tend to disperse." This phrasing is awkward and could benefit from clarification.

This will be fixed to spell: “Our key observation is that tokens linked to semantically similar regions form metastable states, i.e., regions where attention tends to concentrate, while noisy attention scores dissipate.”

L12-13: "We demonstrate that using it brings improvements in unconditional image generation." It would be more informative to include specific quantitative results.

We agree it is useful to mention in what aspects did the unconditional generation improve, but since this application is only one of many downstream tasks that our conceptual framework improves, we will fix this sentence to spell: “We show that TokenRank enhances unconditional image generation, improving both quality (IS) and diversity (FID)”.

L37: "(non-negative)". I'm not sure why this is in parentheses!

We will remove the parentheses.

L55/223: "2nd" should be spelled out

Will be fixed.

L42-43: "we argue that considering direct token relationships is not necessarily best for evaluating importance." This claim would benefit from a few more words.

Thanks. This paragraph draws an analogy between PageRank and our framework, where for webpages, simply counting incoming links will yield a bad metric of overall importance. Similarly, simply using direct attention (row- or column-select) to measure global relevance of a token underperforms compared to propagating it through the chain, as we show in various experiments. This considers indirect attention propagated through multiple bounces, eventually taking into account all indirect attention effects (steady-state). We will refine the paragraph to reflect this.

Section 3.1 discusses convergence to $v_{ss}$, but it would be nice to tie this into the formalized equations where $v_{ss}$ is explicitly shown as a left-hand side variable.

While we can formulate $v_{ss}$ in closed form by taking the limit $v_{ss} = \lim_{n\rightarrow\infty}([1 .. 0 .. 0]\cdot A^n)$, this would be slightly less elegant since we wish for the readers to establish an intuition and familiarity with the power-method approach for later on. We believe it is quite straight forward to see why $v_{ss}$ is reached using the power method when $n\rightarrow\infty$.

L225-227: "we hypothesize that larger values are statistically correlated with the amount of important information..." No statistical test is presented to evaluate this hypothesis.

We appreciate this comment and agree with the suggestion. We hypothesize that the magnitude of the second largest eigenvalue of the attention matrix correlates with the downstream task performance (zero-shot segmentation and linear probing). We illustrated this effect via weighted averaging of heads. To test the significance of our observation, we perform a paired data statistical test, ie, the Wilcoxon test for semantic segmentation and linear probing. For this purpose, we define the null hypothesis: Uniform and $\lambda_2$ weighting have the same performance. And the one-sided alternative hypothesis: $\lambda_2$ weighting results in a better performance.

Semantic segmentation

Linear probing

Rejecting the null hypothesis with $p<0.05$ supports our statements.

L255 + others: So many critical details are offloaded to the supplement.

We apologize for the inconvenience, and will use exact references to the supplementary.

L252-253: "indicating that our method is on par and arguably better than the previous state-of-the-art..." All of the comparisons in this paper lack error bars. Going back to weakness 7, how can anything be "arguably" better?

Thank you for pointing this out. We apologize for the unclear wording. The usage of "arguably" was not related to statistical significance. Instead, while Acc and mAP are largely better, we underperform ConceptAttention for mIOU. We argue that we are better than ConceptAttention (despite the drop in mIOU), as the threshold-agnostic metric mAP shows a large gap in performance. The qualitative results in the supplementary (Fig.7) also illustrate how our attributions are smooth and intuitive, while the ones by ConceptAttention appear to be noisy and over-confident.

However, following the comment about missing error bars, we computed mean and std for the following results:

Semantic segmentation

The error bars (std) are computed over 5 runs with different seeds. We reproduced ConceptAttention using their implementation. The results are lower than the reported ones in their paper. However, the experiments show that different seeds do not have a significant influence on the computed results.

Linear probing (Tab. 2)

Furthermore, we performed a Wilcoxon test with the null hypothesis that the competing column sum operation results in the same accuracy as TokenRank and the one-sided alternative hypothesis that the accuracy is lower. We reject the null hypothesis with p=0.03 (DINOv1) and p=0.03 (DINOv2).

We believe the masking results (Sec. 5.4) are already stable since they were computed based on a set of models.

I would consider trimming less central experiments to allow for deeper analysis of key results.

Thank you for this suggestion. We concur and we will move the probing experiments to the supplementary materials to allow a more elaborate discussion of the key results, particularly considering the effectivness of consdering additional bounces (semantic segmentation) and the evaluation of the global importance via TokenRank.

It's worth citing Ildiz et. al [0] and discussing in the related works where this work differs.

Thank you. Ildiz et. al [0] has slipped under our radar and considers modelling a 1-layer transformer as a Markov chain, and come to the significant conclusion that the output space is generated by transitioning through a recoverable matrix $A$ learned by the transformer, weighted by the frequency of tokens in the input prompt. This means that positional encoding for this case is not important, as the transformer merely assigns probability vectors for every token in the embedding and multiplies them by the frequency of the input prompt to generate a result. There are two main fundamental differences between our studies. First, we focus on large pretrained transformers and model each individual self-attention matrix as a Markov chain, while Ildiz et. al focus on a degenerate case of a single layer, and model the entire transformer pipeline as a Markov chain. While this allows Illdiz et. al to draw some conclusions and explanations regarding the behavior of larger transformers, we explicitly show how our framework allows for the interpretation of existing, pretrained large transformers and for a better performance in various tasks. Secondly, we leverage more of the machinery of the Markov chain theory, including multiple transitions and steady state analysis. This was not considered previously.

We will add this explanation to the related work section.

The authors are providing new theoretical results

We do not believe our study provides any new theoretical results. Our mathematical model and its application are well-understood and explored in other fields. Casting attention into these frameworks constitutes novelty, but not in terms of theory.

there is not enough detail about how the authors ran their experiments to redo them. Which experiments ran on which GPU (of the 4 types used)?

We politely disagree. We do believe the supplement provides details of how to reproduce our experiments, and do not think the GPU type has any effect on our results as long as the models fit into memory (other than the random seed, and performance speed). Furthermore, we are committed to publishing the full implementation of our framework, which will allow accurate reproduction of results. Please note we will also move substantial parts of the implementation details into the main paper, as suggested.

We thank the reviewers for their constructive feedback and ideas. We are happy that the reviewers like the elegant and insightful framework (BdYW) that is grounded in both theoretical insight and empirical validation (pbyL), its effectiveness (BdYW,YchT) and novelty (BdYW,mHJ9,pbyL,YchT), and the clear and well-structured description (mHJ9,pbyL). The provided feedback helps us to improve the paper and we will address the individual concerns raised by reviewer BdYW below.

More validation in NLP or multimodal settings will be helpful to illustrate its effectiveness and domain generality.

Thank you for this comment. While we fully appreciate our study's impact would have been stronger by validating with other modalities, we intentionally focused on extensive and rigorous experimentation on one specific domain for the purpose of anchoring this interpretation as useful and impactful. Exploring the usefulness of our framework for other domains such as NLP, human motion, or video would be an exciting future work prospect.

More ablation studies to evaluate the contributions of individual components are suggested.

We will move the ablation table (Tab. 1 in the supplementary, for semantic segmentation) to the main paper to make it easier for readers to assess the contribution of individual components. If there are specific ablations the reviewer is interested in that do not appear in the table, we commit to providing them.

The discussions about the limitations are insufficient.

We agree with the suggestion to discuss limitations in further detail. The main drawbacks of using our framework are:

• Our formulation is limited to square matrices (e.g. self-attention / hybrid-attention blocks). Therefore, cross-attention blocks do not naturally fit into our Markov chain formulation due to the existence of non-accessible states. There could potentially be a way to resolve this by introducing dummy states with uniformly distributed transition probability.
• The propagation of attention requires to process the attention maps post-process in an “offline” manner. We did not explore (and tend to be skeptical) that our framework can be leveraged to replace or improve a pre-trained transformer to perform its task better.
• Computing the 2nd eigenvalues $\lambda_2$ is very slow due to the inability to leverage rapid decomposition methods that rely on symmetry or PSD. Computing multiple bounces or the TokenRank on the other hand is quite performant, as it relies on vector matrix product operations, and convereges typically after 10 to 20 iterations.
• We observe that the performance gains with TokenRank are smaller for transformers where the attention map is less structured. Consider, e.g., the masking experiment in Tab.4, where TokenRank brings a signficantly larger gain for DINOv2 than for a supervised ViT.

These limitations will be incorporated into the revised manuscript.