The hidden costs of efficient visual representation learning

Abstract

Efficient visual representation learning is a key challenge in modern computer vision. As visual models are increasingly used for high-resolution images and dense prediction tasks, they must capture long-range dependencies without becoming computationally prohibitive. Vision Transformers address this by using self-attention to model global interactions between image patches, but the quadratic complexity of self-attention limits their scalability. This has motivated more efficient alternatives, such as State Space Models (SSMs) and linear attention, which reduce the cost of token interactions. However, computational efficiency alone is not enough for reliable visual representation learning. These models must also be robust to changes in input conditions and expressive enough to capture complex relationships across image regions. This thesis investigates the hidden costs introduced by efficient token interaction mechanisms in visual representation learning. First, we examine the robustness of SSMs under geometric transformations. SSMs process image patches using fixed sequential scan orders, enabling global modeling with linear complexity. However, this design imposes a fixed one-dimensional order on inherently two-dimensional image data. Consequently, the learned representations can become sensitive to the chosen traversal path and unstable under geometric transformations such as rotation. To address this limitation, we introduce Spectral VMamba, a vision SSM that uses spectral decomposition of the graph Laplacian of image patches to define patch traversal according to the intrinsic structure of the image rather than fixed spatial directions. This enables rotation-invariant patch processing while preserving the efficiency advantages of SSMs. Second, we examine the robustness of SSMs under distribution shift, where test images differ from training data due to corruptions, domain changes, or acquisition variability. In SSMs, patches are processed sequentially, and the hidden state at each step carries accumulated context from all previously processed patches. Under distribution shift, corrupted patch embeddings are injected into the hidden state and propagate through all subsequent updates, and because fixed scan orders always inject these artifacts at the same position in the traversal sequence, their influence is consistently amplified rather than diluted. To address this, we propose TRUST, a test-time adaptation method tailored for Mamba-based vision models. TRUST generates complementary causal views of the input via diverse traversal permutations, filters predictions by uncertainty to retain only reliable permutations, and updates Mamba specific parameters at inference time, requiring neither source data nor retraining. This allows the model to adapt its parameters toward more robust representations under shifted test distributions. Third, we address the expressiveness limitations of linear attention. Although linear attention improves scalability by avoiding the quadratic cost of self attention, standard kernelized formulations mainly rely on direct, first-order interactions between tokens. As a result, they may struggle to capture higher-order or transitive relationships between image regions. To overcome this limitation, we introduce LiSA, a Linear Stochastic Attention module that reformulates attention as a truncated random walk over a graph of image patches. Through multi-hop information propagation, LiSA captures richer token relationships while preserving linear complexity and stable training. Across image classification, semantic segmentation, and object detection, the proposed methods improve robustness and representation quality while maintaining computational efficiency. Overall, this thesis shows that efficient visual backbone design should not be evaluated by computational cost alone. Instead, scalability must be considered together with the robustness and expressiveness of token interactions, especially when models are expected to operate reliably under real-world visual variations.

Date	10 Sept 2026
Original language	American English
Awarding Institution	École de technologie supérieure
Supervisor	Christian Desrosiers (Supervisor) & Hervé Lombaert (Co-supervisor)