=== SAMENVATTING ===

Technische Samenvatting: MergeOver

Probleemstelling

Vision Transformers (ViTs) hebben state-of-the-art prestaties bereikt in computer vision, maar worden geconfronteerd met aanzienlijke barrières voor implementatie op middelenbeperkte edge-hardware vanwege enorme parameteraantallen en een kwadratische computationele complexiteit ($O(N^2)$) ten opzichte van de sequentielengte. Hoewel recursieve gewichtsdeling (zoals in de Sliced Recursive Transformer, SReT) het aantal parameters effectief vermindert door gewichten te hergebruiken over meerdere passes, verergert dit de computationele knelpunten en de Peak Activation Memory (PAM). Daarentegen biedt Token Merging (ToMe) een post-training mechanisme om de sequentielengte te verminderen en deze knelpunten te verzachten.

Het integreren van deze twee paradigma's is echter niet triviaal. Directe integratie creëert ernstige architecturale frictie:

1. Ruimtelijke beperkingen: SReT vertrouwt op hiërarchische convolutionele poolinglagen die rigide 2D-ruimtelijke roosters vereisen. Standaard token merging vernietigt de perfect vierkante eigenschap van de sequentielengte, wat leidt tot dimensionale conflicten.
2. Groeperingsbeperkingen: De Sliced Group Self-Attention (SGA) van SReT vereist dat sequentielengtes deelbaar zijn door specifieke groepsgroottes. Onbeperkt mergen schendt deze grenzen.
3. Tracking-beperkingen: SReT gebruikt ruimtelijke permutaties om aandachtvensters te verschuiven. ToMe vertrouwt op een token-massa vector om proportionele aandacht te behouden; als deze vector niet synchroon met de features wordt gepermuteerd, wordt het aandachtmechanisme gecorrumpeerd.

Bestaande efficiënte architecturen vereisen vaak hertraining, distillatie of structurele herontwerp, wat een gat laat voor post-training compressie methoden die recursieve gewichtsdeling combineren met dynamische tokenreductie.

Methodologie: MergeOver

De auteurs stellen MergeOver voor, een post-training benadering die ToMe integreert in SReT zonder hertraining. De methodologie adresseert de drie incompatibiliteiten via specifieke mechanismen:

1. Unmerge Tracking Stack (Oplossen van ruimtelijke beperkingen)

Om aan de geometrische vereisten van inter-stage convolutionele pooling te voldoen, implementeert MergeOver een Unmerge stack.

• Mechanisme: Tijdens een stage, wanneer tokens worden samengevoegd, wordt de bijbehorende "Unmerge" operatie (die samengevoegde features terugdupliceert naar hun oorspronkelijke ruimtelijke coördinaten) op een Last-In-First-Out (LIFO) stack geplaatst.
• Restauratie: Voordat de sequentie de inter-stage convolutionele poolinglaag ingaat, wordt de stack gepopt en worden de Unmerge operaties in omgekeerde volgorde toegepast. Dit herstelt de sequentie naar de oorspronkelijke lengte en het 2D-rooster, waardoor de convolutionele kernels correct kunnen opereren terwijl de Transformer-blokken een gecomprimeerde sequentie verwerken.

2. Constraint-Safe Merge-Rate Adjustment (Oplossen van groeperingsbeperkingen)

De merge-rate ($r$) kan niet willekeurig zijn. Het moet voldoen aan:

• Deelbaarheid: De resulterende sequentielengte ($N-r$) moet deelbaar zijn door het kleinste gemene veelvoud (LCM) van de groepsgroottes ($g$) die worden gebruikt in de huidige en de volgende recursieve iteraties.
• Bipartite Limieten: ToMe's Bipartite Soft Matching (BSM) kan niet meer dan de helft van de tokens in een enkele iteratie samenvoegen ($r \le \lfloor N/2 \rfloor$).
• Implementatie: De doelreductie wordt aangepast naar de dichtstbijzijnde "veilige" waarde ($r_{safe}$) die voldoet aan $(N-r) \mod g = 0$ en $N-r \ge g$.

3. Synchronized Token-Mass Tracking (Oplossen van tracking-beperkingen)

Om proportionele aandacht te behouden tijdens de ruimtelijke permutaties van SReT:

• Een token-massa tensor ($s$) wordt geïnitialiseerd als enen en wordt over lagen heen bijgewerkt om het aantal originele patches te volgen dat elk token vertegenwoordigt.
• Synchronisatie: De massa-tensor wordt parallel door exact dezelfde permutatie- en inverse permutatiefuncties gerouteerd als de feature-sequentie. Dit zorgt ervoor dat de gewichten die worden gebruikt in de aandachtberekening (Vergelijking 2) uitgelijnd blijven met hun overeenkomstige tokens.
• Gewogen Merging: Merging wordt uitgevoerd via een gewogen gemiddelde met behulp van de massa-tensor om te voorkomen dat "zware" tokens ondervertegenwoordigd raken.

4. Token Reduction Scheduling

Het artikel evalueert vier scheduling-strategieën om de optimale reductie-traject te bepalen:

• Global Schedules: Constant en lineair afnemend (standaard ToMe baselines).
• Stage-wise Schedules:
  • Exponentieel: Progressief kleinere reducties binnen een stage.
  • Single-shot: Token reductie vindt alleen plaats bij het eerste blok van elke stage, waardoor een vaste sequentielengte behouden blijft voor daaropvolgende recursieve iteraties binnen die stage.

Belangrijkste Bijdragen

1. MergeOver Formulering: Een post-training framework dat token merging mogelijk maakt binnen hiërarchische recursieve transformers zonder hertraining.
2. Architecturale Integratie: Het oplossen van de specifieke incompatibiliteiten tussen de ruimtelijke/aandachtsbeperkingen van SReT en de merging-logica van ToMe via Unmerge stacks en gesynchroniseerde massa-tracking.
3. Scheduling Analyse: Een evaluatie van token reductie strategieën, waarbij een stage-wise single-shot strategie wordt geïdentificeerd als de meest compatibele met de SReT-architectuur.
4. Cross-Platform Benchmarking: Een uitgebreide evaluatie op ImageNet-1K over GPU, x86 CPU en ARM CPU (Raspberry Pi 5) platforms.

Experimentele Resultaten

Geëvalueerd op de ImageNet-1K validatieset met behulp van de SReT-Tiny-Distill baseline:

Nauwkeurigheid vs. Efficiëntie Trade-off

• Geselecteerde Configuratie: De stage-wise single-shot schedule met een initiële reductiefractie van $\rho_{shot} = 0.25$.
• Nauwkeurigheid: Vermindert de Top-1 nauwkeurigheid met slechts 1,47 procentpunt (van 77,39% naar 75,92%).
• FLOPs: Vermindert de theoretische FLOPs met 22,0%.

Hardware Prestaties (Batch Grootte 16)

• GPU (RTX 4060 Ti):
  • Throughput: Neemt toe met 21,7%.
  • Peak Activation Memory (PAM): Vermindert met 38,4%.
  • Opmerking: Bij Batch Grootte 1 neemt de throughput af met 21,7% door overhead, wat aangeeft dat de methode de voorkeur geeft aan gebatteerde executie op GPU's.
• x86 CPU (Intel Core Ultra 9):
  • Latency: Vermindert met 30,0%.
  • Throughput: Neemt toe met 42,9% (waargenomen in de agressieve $\rho_{shot}=0.40$ configuratie, die een nauwkeurigheidsverlies van 5,03% met zich meebrengt).
  • Geheugen: De Process Resident Set Size ($\Delta$RSS) neemt af met 22,0%.
  • Opmerking: In tegenstelling tot de GPU versnelt MergeOver single-stream inference (Batch Grootte 1) op x86, waarbij de latency met 17,9% afneemt.
• ARM CPU (Raspberry Pi 5):
  • Latency: Vermindert met 17,6% bij Batch Grootte 16 (en 2,4% bij Batch Grootte 1).
  • Throughput: Neemt toe met 21,4% bij Batch Grootte 16.
  • Geheugen: $\Delta$RSS neemt af met 39,6% bij Batch Grootte 16.

Betekenis en Claims

Het artikel claimt dat MergeOver erin slaagt de kloof tussen recursieve gewichtsdeling en token merging te overbruggen, een combinatie die voorheen onverkend was. De primaire betekenis ligt in:

1. Post-Training Levensvatbaarheid: Het demonstreert dat complexe architecturale integraties kunnen worden bereikt zonder de kosten van hertraining, distillatie of structurele herontwerp.
2. Efficiëntie Herstellen: Het herstelt een aanzienlijk deel van de throughput en geheugenkosten die door recursieve gewichtsdeling worden geïntroduceerd, waardoor recursieve modellen levensvatbaarder worden voor edge-implementatie.
3. Platform Afhankelijkheid: De resultaten benadrukken dat de voordelen van token reductie sterk afhankelijk zijn van het verwerkingsplatform en de batch grootte. Terwijl single-stream GPU inference lijdt onder overhead, tonen gebatteerde executie en CPU-gebaseerde edge-devices (x86 en ARM) substantiële latency en geheugenverbeteringen.
4. Baseline Vaststelling: MergeOver biedt een fundamentele baseline voor het combineren van token merging met hiërarchische recursieve transformers, wat de weg vrijmaakt voor toekomstige low-level kernel optimalisaties en verdere compressietechnieken (bijv. kwantisatie).

De auteurs blijven bescheiden en erkennen dat de evaluatie beperkt is tot het SReT-Tiny-Distill model en dat de geobserveerde prestatiewinsten nog niet geïsoleerd zijn van specifieke architecturale eigenschappen of low-level kernel optimalisaties. Ze positioneren MergeOver als een startpunt voor verder onderzoek naar multi-as compressie voor edge AI.