Attention (as Discrete-Time Markov) Chains

• URL: http://arxiv.org/abs/2507.17657v1
• Date: Wed, 23 Jul 2025 16:20:47 GMT
• Title: Attention (as Discrete-Time Markov) Chains
• Authors: Yotam Erel, Olaf Dünkel, Rishabh Dabral, Vladislav Golyanik, Christian Theobalt, Amit H. Bermano,
• Abstract summary: We introduce a new interpretation of the attention matrix as a discrete-time Markov chain.<n>Our main observation is that tokens corresponding to semantically similar regions form a set of metastable states.<n>Using these lightweight tools, we demonstrate state-of-the-art zero-shot segmentation.
• Score: 70.46604474584181
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new interpretation of the attention matrix as a discrete-time Markov chain. Our interpretation sheds light on common operations involving attention scores such as selection, summation, and averaging in a unified framework. It further extends them by considering indirect attention, propagated through the Markov chain, as opposed to previous studies that only model immediate effects. Our main observation is that tokens corresponding to semantically similar regions form a set of metastable states, where the attention clusters, while noisy attention scores tend to disperse. Metastable states and their prevalence can be easily computed through simple matrix multiplication and eigenanalysis, respectively. Using these lightweight tools, we demonstrate state-of-the-art zero-shot segmentation. Lastly, we define TokenRank -- the steady state vector of the Markov chain, which measures global token importance. We demonstrate that using it brings improvements in unconditional image generation. We believe our framework offers a fresh view of how tokens are being attended in modern visual transformers.

Related papers

• Artifacts and Attention Sinks: Structured Approximations for Efficient Vision Transformers [8.486148475471271]
  Vision transformers have emerged as a powerful tool across a wide range of applications, yet their inner workings remain only partially understood.<n>We examine the phenomenon of massive tokens - tokens with exceptionally high activation norms that act as attention sinks - and artifact tokens that emerge as a byproduct during inference.<n>We introduce Fast Nystr"om Attention (FNA), a training-free method that approximates self-attention in linear time and space.
  arXiv  Detail & Related papers  (2025-07-21T19:29:03Z)
• "Principal Components" Enable A New Language of Images [79.45806370905775]
  We introduce a novel visual tokenization framework that embeds a provable PCA-like structure into the latent token space.<n>Our approach achieves state-of-the-art reconstruction performance and enables better interpretability to align with the human vision system.
  arXiv  Detail & Related papers  (2025-03-11T17:59:41Z)
• Repurposing Stable Diffusion Attention for Training-Free Unsupervised Interactive Segmentation [1.878433493707693]
  Recent progress in interactive point prompt based Image allows to significantly reduce the manual effort to obtain high quality semantic labels.<n>We propose a novel unsupervised and training-free approach based solely on the self-attention of Stable Diffusion.
  arXiv  Detail & Related papers  (2024-11-15T18:29:59Z)
• iSeg: An Iterative Refinement-based Framework for Training-free Segmentation [85.58324416386375]
  We present a deep experimental analysis on iteratively refining cross-attention map with self-attention map. We propose an effective iterative refinement framework for training-free segmentation, named iSeg. Our proposed iSeg achieves an absolute gain of 3.8% in terms of mIoU compared to the best existing training-free approach in literature.
  arXiv  Detail & Related papers  (2024-09-05T03:07:26Z)
• Semantic Equitable Clustering: A Simple and Effective Strategy for Clustering Vision Tokens [57.37893387775829]
  We introduce a fast and balanced clustering method, named Semantic Equitable Clustering (SEC)<n>SEC clusters tokens based on their global semantic relevance in an efficient, straightforward manner.<n>We propose a versatile vision backbone, SECViT, to serve as a vision language connector.
  arXiv  Detail & Related papers  (2024-05-22T04:49:00Z)
• From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers [41.82477691012942]
  We study learning a 1-layer self-attention model from a set of prompts and associated output data. We first establish a precise mapping between the self-attention mechanism and Markov models. We characterize an intriguing winner-takes-all phenomenon where the generative process implemented by self-attention collapses into sampling a limited subset of tokens.
  arXiv  Detail & Related papers  (2024-02-21T03:51:34Z)
• Causal structure learning with momentum: Sampling distributions over Markov Equivalence Classes of DAGs [4.811183825795439]
  We devise a non-reversible continuous time Markov chain that targets a probability distribution over classes of DAGs. We develop new algorithms for listing, counting, uniformly sampling, and applying possible moves of the GES operators.
  arXiv  Detail & Related papers  (2023-10-09T12:10:51Z)
• Generic Attention-model Explainability by Weighted Relevance Accumulation [9.816810016935541]
  We propose a weighted relevancy strategy, which takes the importance of token values into consideration, to reduce distortion when equally accumulating relevance. To evaluate our method, we propose a unified CLIP-based two-stage model, named CLIPmapper, to process Vision-and-Language tasks.
  arXiv  Detail & Related papers  (2023-08-20T12:02:30Z)
• Measuring the Interpretability of Unsupervised Representations via Quantized Reverse Probing [97.70862116338554]
  We investigate the problem of measuring interpretability of self-supervised representations. We formulate the latter as estimating the mutual information between the representation and a space of manually labelled concepts. We use our method to evaluate a large number of self-supervised representations, ranking them by interpretability.
  arXiv  Detail & Related papers  (2022-09-07T16:18:50Z)
• Provably End-to-end Label-Noise Learning without Anchor Points [118.97592870124937]
  We propose an end-to-end framework for solving label-noise learning without anchor points. Our proposed framework can identify the transition matrix if the clean class-posterior probabilities are sufficiently scattered.
  arXiv  Detail & Related papers  (2021-02-04T03:59:37Z)
• Bayesian Attention Modules [65.52970388117923]
  We propose a scalable version of attention that is easy to implement and optimize. Our experiments show the proposed method brings consistent improvements over the corresponding baselines.
  arXiv  Detail & Related papers  (2020-10-20T20:30:55Z)
• Learning Hard Retrieval Decoder Attention for Transformers [69.40942736249397]
  Transformer translation model is based on the multi-head attention mechanism, which can be parallelized easily. We show that our hard retrieval attention mechanism is 1.43 times faster in decoding.
  arXiv  Detail & Related papers  (2020-09-30T13:18:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.