StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything

Each square is a patch token of SAM's image encoder, laid out on the H×W patch grid, painted with 2–3 object regions on a flat background (each token's feature is a region signature plus noise) and a prompt box over one object. StructSAM's real energy score is computed live: the first-order feature-gradient energy G(h,w) = √(‖∇_xf‖² + ‖∇_yf‖²) from central differences on the feature map, so high G = a boundary/edge token (amber edge, protect) and low G = a flat region (safe to merge). StructSAM runs grid-based flatness screening: tokens with G above the margin threshold (and, in prompt-aware mode, the prompt tokens) are protected (teal / pink rings); the remaining flat tokens are merged toward the low-energy (argmin G) destination by a size-weighted average (the number in a merged token is the patches it now represents), and a merge-unmerge / recovery step duplicates the destination feature back to the cell so the decoder still sees a dense grid (the patch colours you see are that lifted feature map). Naive ToMe is window-restricted with no screening: it collapses each window toward a structure-agnostic destination, so it absorbs boundary and prompt tokens and its contours bleed. The right panel is the money shot. It builds the normalized Laplacian L = I − D^−1/2 A D^−1/2 of the token graph and, following the paper's spectral graph coarsening view, compares the leading eigenvalues of the original grid against the lifted (unmerged) grid, reporting a running spectral distance SD = Σ|λ_i − λ̂_i| and a running structure distance (boundary-map distortion ‖G − Ĝ‖). Because StructSAM only merges inside coherent flat regions, both stay near zero (bounded Laplacian distortion, Theorem 1); naive ToMe erodes boundaries and leaks prompts, so both climb. Turn on Prompt-aware to protect the prompt tokens and merge the background harder (the extra FLOPs saved appear in the readout). (This is a 2D didactic illustration of the exact mechanism: the gradient-energy score, the flatness / prompt screening, the low-energy merge, the merge-unmerge recovery, and the normalized-Laplacian spectral distance are all computed live on a synthetic patch grid. Honest toy simplifications: tokens are hand-painted region patches, not real SAM ViT features; "attention" is not run (there is no encoder or mask decoder), so "structure distance" is a boundary-map proxy for mask mIoU, not an IoU against ground truth; FLOPs are an analytic n² estimate from token count, not a GPU benchmark; the eigen-decomposition is exact but on a small toy graph, so absolute SD values are illustrative; and merging is shown as one progressive pass rather than the encoder's per-layer margin schedule. In the published method the merge happens inside SAM's ViT image encoder. Across eight natural and medical benchmarks StructSAM cuts encoder FLOPs by 25–30% (up to 40%+ with prompt-aware merging) with only minor mIoU/Dice drops, consistently outperforming ToMe, PiToMe, ToMeSD, VidToMe and ALGM at the same compute, and a StructSAM + OpenVLA robotics variant matches SAM-2 tracking with a ~45% speedup. TrungTin Nguyen is a co-author.)