Bidirectional Scan for Vision

mediumPROVision MambaArray, AlgorithmsAdvanced Architectures

Vision Mamba processes image patches bidirectionally to capture both forward and backward context, unlike the causal (left-to-right only) scanning in language models.

For a 1D sequence $x = [x_1, x_2, ..., x_N]$ :

Forward scan: Cumulative sum from left to right
Backward scan: Cumulative sum from right to left
Output: Element-wise sum of forward and backward scans

This bidirectional approach ensures each patch attends to information from both directions, crucial for non-causal tasks like image classification.

Task: Implement the bidirectional scan fusion.

Example

Input

x = [1.0, 2.0, 3.0, 4.0]

Output

[11.0, 12.0, 13.0, 14.0]

Reasoning

Input: x is a 1D sequence of $N = 4$ patch values, $x = [1, 2, 3, 4]$ . The output has the same length: one fused value per patch.
Forward scan: position $i$ holds the running total from the left end up to and including $x_i$ : $1$ , $1+2=3$ , $3+3=6$ , $6+4=10$ , giving $[1, 3, 6, 10]$ .
Backward scan: position $i$ holds the total from $x_i$ to the right end: $4$ , $3+4=7$ , $2+7=9$ , $1+9=10$ , so read left to right it is $[10, 9, 7, 4]$ .
Fusion: add the two scans position by position: $1+10=11$ , $3+9=12$ , $6+7=13$ , $10+4=14$ , which is the output [11.0, 12.0, 13.0, 14.0].
Notice that $x_i$ is the only element counted by both scans, so each output equals $\sum_j x_j + x_i = 10 + x_i$ . Every patch sees the whole sequence, plus an extra copy of itself. That is why an all-ones input of length 4 gives $4 + 1 = 5$ everywhere.

Constraints

Sequence length $N$ : $1 \leq N \leq 1000$
Values are floats

More from Advanced Architectures

Complete Mixer Block with Residualshard Channel Mixing with GELUmedium Token Mixing Layermedium Discretize Continuous State Space Modelhard State Space Model vs Attention Complexitymedium

Concept primerPREVIEW

Bidirectional Scan for Vision

Background Knowledge

In language models, causal (unidirectional) scanning ensures the model only sees past tokens when predicting the next one. However, images have no inherent directionality - every pixel should be able to attend to every other pixel.

Why Bidirectional?

Domain	Scanning	Reason
Language	Causal (→)	Can't see future tokens during generation
Vision	Bidirectional (↔)	All patches are available simultaneously

Vision Mamba's Approach

Vision Mamba adapts the Mamba architecture for vision by:

Running a forward scan (left-to-right)
Running a backward scan (right-to-left)
Fusing both scan outputs (typically addition)

This gives each patch access to global context while maintaining $O(N)$ complexity.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

Example

Constraints

More from Advanced Architectures

Bidirectional Scan for Vision

Background Knowledge

Why Bidirectional?

Vision Mamba's Approach

Continue the full explanation

Editor locked