Why 1 + 1 < 1 in Visual Token Pruning: Beyond Naive Integration via Multi-Objective Balanced Covering

Dit paper introduceert MoB, een methode voor visuele token-pruning die het inherente compromis tussen prompt-uitlijning en visuele behoud oplost door het probleem te herformuleren als een bi-objectief overdekkingsprobleem, wat leidt tot aanzienlijke versnelling van multimodale modellen met minimaal prestatieverlies.

De kern

Stel je voor dat een Multimodaal Groot Taalmodel (MLLM) als een zeer intelligente, maar soms wat vergetelijke detective is. Deze detective moet een foto bekijken en een vraag beantwoorden. Het probleem? De foto bestaat uit duizenden kleine stukjes (tokens), en de detective moet elk stukje lezen om het antwoord te vinden. Dit kost enorm veel tijd en rekenkracht, alsof je elke steen op de grond van een stad moet tellen om te weten of er een auto in staat.

Om dit sneller te maken, proberen onderzoekers "visuele token pruning" toe te passen. Dat is een fancy manier van zeggen: "Laat de detective alleen de belangrijkste stukjes van de foto bekijken en gooi de rest weg."

Eerdere methoden deden dit op twee manieren:

1. Bewaar de details: Houd de stukjes vast die het mooist of het meest informatief zijn (bijvoorbeeld een heldere auto of een gezicht).
2. Blijf bij de vraag: Houd alleen de stukjes vast die direct te maken hebben met de vraag (bijvoorbeeld als de vraag is "Wat is de kleur van de auto?", dan houd je alleen de auto vast).

Het probleem is dat eerdere methoden deze twee strategieën vaak simpelweg bij elkaar optelden. Ze dachten: "Als we beide doen, is het dubbel zo goed." Maar in de praktijk bleek dat niet altijd te werken. Soms werkte het prima, soms viel het tegen. Het was alsof je probeert een auto te bouwen door willekeurig de beste wielen en de beste motor te kiezen, zonder te kijken of ze wel bij elkaar passen.

De doorbraak: De "MoB" methode

De auteurs van dit papier hebben bedacht dat er een diepere, wiskundige relatie is tussen de vraag en de foto. Ze noemen dit de "koppeling" (coupling).

Stel je voor dat je een puzzel maakt:

• Situatie A (Sterke koppeling): Je hebt een foto van een hond en de vraag is "Wat is dit?". De hond staat precies in het midden. De vraag en de foto zijn heel sterk met elkaar verbonden. In dit geval hoef je niet heel precies te kijken naar de vraag; als je gewoon de belangrijkste delen van de foto (de hond) bewaart, is het antwoord vaak al duidelijk.
• Situatie B (Zwakke koppeling): Je hebt een foto van een drukke markt en de vraag is "Hoeveel appels staan er in de winkel rechts?". De vraag is heel specifiek en de foto is heel breed. De vraag en de foto zijn ver uit elkaar. Hier moet je heel precies kijken naar de vraag om te weten welke stukjes van de foto je moet bewaren. Anders mis je de appels.

De oplossing: MoB (Multi-Objective Balanced Covering)

De nieuwe methode, MoB, werkt als een slimme manager die voor elke situatie een ander plan maakt. In plaats van een vast recept te gebruiken, kijkt MoB eerst naar de "afstand" tussen de vraag en de foto.

• De Analogie van de Tent:
  Stel je voor dat je een tent moet opzetten over een groep mensen (de foto) en een spreker (de vraag). Je hebt een beperkt aantal palen (rekenkracht) om de tent te steunen.
  • Als de spreker dicht bij de mensen staat (sterke koppeling), hoef je de tent niet heel strak rond de spreker te spannen. Je kunt de palen gebruiken om de hele tent stevig te maken over de mensen heen.
  • Als de spreker ver weg staat (zwakke koppeling), moet je eerst een heel stevig touw trekken van de spreker naar de mensen, zodat je weet waar je de tent moet bouwen. Je moet meer palen gebruiken om die verbinding te maken.

MoB verdeelt zijn "palen" (rekenkracht) slim:

1. Het kijkt eerst hoeveel "palen" nodig zijn om de vraag te koppelen aan de foto.
2. De rest van de palen gebruikt het om de foto zelf zo goed mogelijk af te dekken.

Waarom is dit geweldig?

• Het werkt altijd: Of je nu een simpele vraag hebt over een hond of een complexe vraag over een drukke markt, MoB past zich aan.
• Het is snel: Omdat het slim verdeelt, kan het de detective (het model) 1,3 tot 1,5 keer sneller laten werken, zonder dat hij veel fouten maakt.
• Het is bewezen: De auteurs hebben wiskundige formules bedacht die bewijzen dat deze verdeling de beste is die je kunt krijgen met de beschikbare middelen.

Kortom:
Vroeger probeerden we een foto te versnellen door willekeurig stukjes weg te gooien of door twee vaste regels te volgen. Met MoB kijken we eerst naar de relatie tussen de vraag en de foto, en verdelen we onze middelen precies daar waar ze het hardst nodig zijn. Het is alsof we van een statische camera zijn gegaan naar een slimme cameraman die weet waar hij moet focussen, afhankelijk van wat er op het scherm gebeurt.

Dit betekent dat we in de toekomst snellere en slimmere AI-apps kunnen hebben op onze telefoons, die zelfs complexe vragen over video's en foto's kunnen beantwoorden zonder te bevriezen.

Technische samenvatting

Probleemstelling

Multimodale grote taalmodellen (MLLMs) zoals LLaVA en Qwen2-VL presteren uitstekend in visueel-taaltaken, maar lijden onder een hoge rekenkundige overhead. Dit komt doordat visuele data (bijvoorbeeld hoge resolutie afbeeldingen of video's) veel meer tokens genereert dan tekstuele data, wat leidt tot een kwadratische schaalbaarheid van de attention-mechanismen.

Om dit op te lossen, wordt visuele token pruning (het verwijderen van minder belangrijke visuele tokens) gebruikt. Bestaande methoden richten zich doorgaans op twee doelen:

1. Visuele Behoud (Visual Preservation - VP): Tokens behouden die visueel het meest relevant zijn (bijv. door redundantie te minimaliseren).
2. Prompt-uitlijning (Prompt Alignment - PA): Tokens selecteren die het meest relevant zijn voor de gebruikersprompt.

Het paper identificeert een fundamenteel probleem: bestaande multi-objectieve methoden die VP en PA proberen te combineren met statische strategieën, presteren vaak slechter dan methoden die zich op slechts één doel richten. De auteurs noemen dit het "1 + 1 < 1"-fenomeen. De reden hiervoor is dat de relatieve belangrijkheid van VP en PA varieert afhankelijk van de koppeling tussen prompt en visuele input (prompt-visual coupling), wat door eerdere methoden wordt genegeerd.

Methodologie

De auteurs introduceren een nieuwe theoretische en praktische aanpak, Multi-Objective Balanced Covering (MoB), gebaseerd op meetkunde en de theorie van $\epsilon$-overdekking (covering theory).

1. Theoretische Basis: Foutgrenzen en Koppeling

• Hausdorff-afstand: De auteurs formuleren de eerste gesloten-vorm foutgrens voor visuele token pruning, gebaseerd op de Hausdorff-afstand ($d_H$) tussen de originele en de geprende tokensets.
• Prompt-Visual Coupling: Ze definiëren een koppelingsparameter $\eta = d_H(V, P)$, de afstand tussen visuele tokens ($V$) en prompt-tokens ($P$).
  • Zwakke koppeling (Grote $\eta$): De prompt is specifiek en verwijst naar kleine, kritieke gebieden in de afbeelding (bijv. tekstvragen over specifieke objecten). Hier is Prompt Alignment (PA) cruciaal.
  • Sterke koppeling (Kleine $\eta$): De prompt is algemeen en veel visuele gebieden zijn relevant (bijv. algemene beschrijvingen). Hier is Visuele Behoud (VP) efficiënter.
• Intrinsieke Trade-off: Door de budgetbeperking (het totale aantal te behouden tokens $K$) en de koppelingsparameter $\eta$ te analyseren, tonen ze aan dat er een intrinsieke afweging bestaat. Het optimaliseren van beide doelen tegelijk met een statische verdeling is suboptimaal.

2. Het MoB-algoritme

MoB herformuleert token pruning als een bi-objectief overdekkingsprobleem. Het doel is om een set behouden tokens $S$ te vinden die bestaat uit twee disjuncte deelsets:

• $S_p$: Tokens die de prompt overdekken (voor PA).
• $S_v$: Tokens die de visuele input overdekken (voor VP).

Het algoritme lost de trade-off op door de verdeling van het budget ($K_p$ voor $S_p$ en $K_v$ voor $S_v$) dynamisch aan te passen aan de koppelingssterkte:

• Selectie van Prompt-centers ($S_p$):
  • Gebruikt een k-voudige Naïeve Nearest-Neighbor (NN) overdekking.
  • Voor elke prompt-token worden de $k$ dichtstbijzijnde visuele tokens geselecteerd als kandidaten.
  • Vervolgens wordt een subset van $K_p$ tokens gekozen die de ergste uitlijning met de prompt maximaliseert. Dit zorgt ervoor dat kritieke gebieden niet gemist worden, zelfs bij zwakke koppeling.
• Selectie van Visuele centers ($S_v$):
  • Gebruikt Farthest Point Sampling (FPS) op de resterende tokens.
  • Dit verspreidt de visuele tokens zo breed mogelijk over de afbeelding om de overdekkingsstraal (en dus de fout) te minimaliseren.
• Budgettoewijzing:
  • De verhouding $K_p/K$ wordt bepaald door de geschatte koppelingsparameter $\eta$. Bij zwakke koppeling wordt meer budget toegewezen aan $S_p$ (PA), bij sterke koppeling aan $S_v$ (VP).

Belangrijkste Bijdragen

1. Eerste gesloten-vorm foutgrens: De auteurs leiden de eerste theoretische foutgrens af voor visuele token pruning, die de bijdragen van VP, PA en prompt-visual coupling kwantificeert.
2. Kwantificering van de Trade-off: Ze bewijzen dat er een optimale bereikingsniveaus voor elk doel bestaat onder een vast budget, afhankelijk van de koppelingssterkte. Dit verklaart waarom statische multi-objectieve methoden falen.
3. MoB-algoritme: Een training-vrije methode die de trade-off reduceert tot een probleem van budgettoewijzing via "greedy radius trading". Het biedt een bewezen prestatiegarantie en heeft lineaire schaalbaarheid ($O(N(L+K)d)$).
4. Uitgebreide Validatie: Experimenten tonen aan dat MoB consistent beter presteert dan zowel single-objective als bestaande multi-objective baselines.

Resultaten

De auteurs hebben MoB getest op diverse MLLMs (LLaVA-1.5-7B, LLaVA-Next-7B, Qwen2-VL-7B, Video-LLaVA-7B) en 14 benchmarks (inclusief MMBench, POPE, VQAT, etc.).

• Prestatiebehoud:
  • Bij LLaVA-1.5-7B met een tokenreductie van 88,9% (alleen 11,1% van de tokens behouden), behoudt MoB 96,4% van de oorspronkelijke prestatie. Dit is een verbetering van 2,7% ten opzichte van de beste bestaande methode.
  • Bij Video-LLaVA-7B met een reductie van 93,4% (alleen 6,6% tokens), wordt 97,9% van de prestatie behouden.
• Snelheid:
  • MoB versnelt LLaVA-Next-7B met 1,3x tot 1,5x met verwaarloosbaar prestatieverlies.
  • Het is efficiënter dan attention-gebaseerde methoden omdat het geen attention-scores hoeft te berekenen voor elke token, wat compatibel is met Flash Attention.
• Robuustheid: MoB presteert goed op zowel "zwakke koppeling" taken (zoals TextVQA) als "sterke koppeling" taken (zoals MMBench), terwijl andere methoden vaak in één van deze scenario's falen.

Betekenis en Impact

Dit paper is significant omdat het een fundamenteel inzicht biedt in waarom het simpelweg samenvoegen van verschillende pruning-doelen vaak niet werkt. Door de prompt-visual coupling te modelleren en de budgettoewijzing dynamisch aan te passen, biedt MoB een theoretisch onderbouwde en praktische oplossing voor de efficiëntieproblemen van multimodale modellen.

De methode is training-vrij, wat betekent dat het direct toegepast kan worden op bestaande state-of-the-art modellen zonder extra trainingskosten. Dit maakt het zeer waardevol voor het implementeren van MLLMs op resource-beperkte apparaten (zoals mobiele telefoons of edge devices) en voor toepassingen die lage latentie vereisen, zoals AR/VR en autonome navigatie. De theoretische inzichten kunnen ook van toepassing zijn op andere domeinen met hoge redundantie, zoals point clouds en multi-sensor fusie.