ForestPrune: High-ratio Visual Token Compression for Video Multimodal Large Language Models via Spatial-Temporal Forest Modeling

Das Paper stellt ForestPrune vor, eine trainingsfreie Methode zur hochratigen Token-Komprimierung für Video-MLLMs, die durch die Modellierung semantischer, räumlicher und zeitlicher Zusammenhänge in „Token-Wäldern" eine globale Optimierung der Pruning-Entscheidungen ermöglicht und dabei sowohl die Genauigkeit als auch die Effizienz im Vergleich zu bestehenden Verfahren signifikant verbessert.

Das Wesentliche

ForestPrune: Der „Wald-Manager" für Video-KI

Stell dir vor, eine moderne KI, die Videos versteht (wie ein sehr intelligenter Filmkritiker), ist wie ein Student, der versucht, einen 2-stündigen Film zu analysieren. Das Problem: Um den Film zu verstehen, schaut sich die KI jeden einzelnen Bildpunkt (Pixel) in jedem einzelnen Frame an. Bei einem langen Video sind das Millionen von Datenpunkten. Das ist, als würde man versuchen, einen Roman zu lesen, indem man jeden einzelnen Buchstaben einzeln und langsam betrachtet – es dauert ewig und braucht riesige Mengen an Energie (Rechenleistung).

Bisherige Methoden, um diese KI schneller zu machen, waren wie ein Stempel, der auf jedes einzelne Bild schlägt: „Dieses Bild ist wichtig, behalte es! Dieses Bild ist langweilig, wirf es weg!" Das Problem dabei: Wenn man sich einen Film ansieht, wiederholen sich viele Szenen. Ein Gesicht, das im Bild 1, 2 und 3 zu sehen ist, wird von alten Methoden dreimal als „wichtig" markiert und dreimal gespeichert. Das ist wie dreimal denselben Satz in ein Tagebuch zu schreiben, nur weil er in drei aufeinanderfolgenden Zeilen steht. Das spart kaum Platz.

Die neue Lösung: ForestPrune (Der Wald-Manager)

Die Forscher aus Xiamen haben eine clevere Idee namens ForestPrune entwickelt. Statt die Bilder einzeln zu betrachten, schauen sie sich das ganze Video als einen Wald an.

Hier ist die einfache Erklärung, wie das funktioniert:

1. Der Wald statt der Bäume:
   Stell dir vor, jeder Frame (Bild) im Video ist ein Baum. Aber diese Bäume sind nicht isoliert. Sie sind durch unsichtbare Wurzeln miteinander verbunden, die die Zeit und den Ort verbinden. Wenn ein Charakter im Video von links nach rechts läuft, sind die Bäume (Frames) an diesen Positionen miteinander verwachsen.

2. Die Familie der Bäume (Der „Forest"):
   ForestPrune gruppiert diese Bäume zu Familien. Wenn sich in drei aufeinanderfolgenden Frames fast nichts ändert (z. B. eine Person steht nur da und redet), bilden diese Frames einen einzigen, dichten „Baumstamm" im Wald.

3. Der kluge Gärtner (Das Beschneiden):
   Jetzt kommt der Gärtner ins Spiel. Sein Job ist es, den Wald zu beschneiden, damit er leichter zu transportieren ist, ohne dass die Bäume sterben.

   • Alte Methode: Der Gärtner schneidet einfach die unteren Äste jedes einzelnen Baumes ab. Das Ergebnis: Man hat viele kleine, unvollständige Bäume, aber immer noch viele davon.
   • ForestPrune: Der Gärtner schaut sich den ganzen Wald an. Er erkennt: „Aha, dieser ganze Stamm besteht aus fast identischen Ästen über die Zeit hinweg." Anstatt jeden Ast einzeln zu prüfen, schneidet er die überflüssigen Blätter (die redundanten Daten) direkt aus dem Stamm heraus. Er behält nur die wichtigsten „Knotenpunkte" (die Wurzeln und den Hauptstamm), die die Geschichte erzählen.

Warum ist das genial?

• Zeit sparen: Da die KI nicht mehr Millionen von fast gleichen Bildern verarbeiten muss, läuft sie extrem schnell.
• Platz sparen: Man kann das Video um 90 % komprimieren (also 90 % der Daten wegwerfen), und die KI versteht den Film trotzdem fast genauso gut wie vorher.
• Kein Training nötig: Das Beste ist: Man muss die KI nicht neu lernen lassen. ForestPrune ist wie ein cleveres Werkzeug, das man einfach davor hält, bevor die KI das Video verarbeitet.

Ein Beispiel aus dem Papier:
Stell dir vor, in einem Video fragt jemand: „Wie verändert sich der Gesichtsausdruck der Frau?"

• Eine alte Methode (wie G-Prune) würde vielleicht die ersten drei Frames behalten, in denen die Frau überrascht ist, und dann die nächsten drei Frames, in denen sie frustriert ist. Aber sie würde die Frames dazwischen, die fast identisch sind, doppelt speichern.
• ForestPrune erkennt: „Die ersten drei Frames sind ein einziger 'Überraschungs-Stamm'. Die nächsten drei sind ein 'Frust-Stamm'." Es speichert nur die Kerninformationen dieser Stämme. Das Ergebnis: Die KI weiß immer noch genau, dass die Frau von „Überraschung" zu „Frust" wechselt, aber sie hat nur einen Bruchteil der Daten verarbeitet.

Zusammenfassung:
ForestPrune ist wie ein intelligenter Filmredakteur, der nicht einfach zufällige Szenen wegschneidet, sondern die Geschichte des Videos versteht. Er erkennt, wo sich Dinge wiederholen, und entfernt die Wiederholungen geschickt, während er die wichtigen Momente (die Wurzeln des Waldes) intakt lässt. So wird die KI schneller, spart Energie und bleibt trotzdem schlau.

Technische Zusammenfassung

1. Problemstellung

Multimodale Large Language Models (MLLMs) haben in den letzten Jahren große Fortschritte bei Bild-Sprache-Aufgaben erzielt. Bei der Verarbeitung von Videos stoßen diese Modelle jedoch auf erhebliche Herausforderungen:

• Hohe Redundanz: Videos bestehen aus vielen Frames, was zu einer quadratischen Zunahme der Rechenkosten und einer massiven visuellen Redundanz führt.
• Limitationen bestehender Methoden: Bestehende Token-Kompressionsverfahren (wie G-Prune oder VisionZip) konzentrieren sich oft auf die Wichtigkeit von Tokens pro Einzelbild (bildbasiert). Sie modellieren die zeitliche Kontinuität und globale Redundanz über mehrere Frames hinweg unzureichend.
• Leistungseinbruch bei hoher Kompression: Während diese Methoden bei moderater Kompression (z. B. 50–70 %) noch akzeptable Ergebnisse liefern, bricht die Genauigkeit bei hohen Kompressionsraten (z. B. 90 %) drastisch ein, da wichtige zeitliche Informationen verloren gehen oder redundante Tokens über mehrere Frames hinweg beibehalten werden.

2. Methodik: ForestPrune

Das Paper stellt ForestPrune vor, eine trainingsfreie Methode zur Token-Pruning, die speziell für Video-MLLMs entwickelt wurde. Der Kernansatz ist die raum-zeitliche Waldmodellierung (Spatial-Temporal Forest Modeling).

Der Prozess läuft in folgenden Schritten ab:

1. Auswahl repräsentativer Knoten:
   Zuerst werden für jeden Frame des Videos repräsentative visuelle Tokens ausgewählt (z. B. durch existierende Pruning-Methoden oder zufällige Sampling). Diese dienen als potenzielle Knoten für den späteren „Wald".

2. Konstruktion des raum-zeitlichen Waldes:
   Anstatt Frames isoliert zu betrachten, werden die Tokens über alle Frames hinweg zu Bäumen verknüpft. Die Verknüpfung basiert auf drei Constraints:

   • Semantische Ähnlichkeit: Tokens mit ähnlichen Merkmalen werden verbunden.
   • Räumliche Nähe: Tokens, die sich im Bild räumlich nahe sind, werden bevorzugt.
   • Zeitliche Ordnung: Die Verbindung erfolgt strikt in zeitlicher Reihenfolge (von früheren zu späteren Frames).

   Dies geschieht durch die Berechnung einer Adjazenzmatrix basierend auf semantischer Distanz und räumlicher Koordinate, gefiltert durch Schwellenwerte ($\tau_s$ für Semantik, $\tau_p$ für Raum).

3. Baumstruktur und Wichtigkeitsbewertung:
   Die resultierenden Strukturen sind Bäume (oder ein Wald), in denen:

   • Wurzelknoten (Roots): Die ersten/ältesten Tokens eines semantischen Pfades.
   • Stammknoten (Trunks): Wichtige Zwischenknoten.
   • Blattknoten (Leaves) & Endknoten (Tails): Spätere, oft redundante Tokens.

   Die Wichtigkeit eines Tokens wird durch seine Tiefe im Baum und seine Rolle definiert. Tiefe Bäume mit Wurzeln und Stämmen werden als global wichtiger erachtet als isolierte Blätter.

4. Pruning-Strategie:
   Basierend auf dem Budget (z. B. 90 % Reduktion) werden die Bäume nach ihrer Tiefe sortiert.

   • Zuerst werden Blattknoten und Endknoten entfernt, da sie oft redundante Informationen enthalten.
   • Erst wenn das Budget nicht erreicht ist, werden Knoten an den Enden der Äste entfernt.
   • Wurzelknoten werden so lange wie möglich erhalten, um die globale zeitliche Struktur zu bewahren.

3. Schlüsselbeiträge

• Raum-zeitliche Modellierung: Das Paper identifiziert die Modellierung der zeitlichen Kontinuität als kritischen Faktor für effektive Video-Kompression, den bisherige Methoden vernachlässigten.
• Trainingsfreie Lösung: ForestPrune erfordert kein Fine-Tuning des MLLMs und ist somit universell einsetzbar.
• Globale Optimierung: Durch die Betrachtung des gesamten Videos als „Wald" trifft das System globale Entscheidungen über die Token-Auswahl, anstatt nur lokal pro Frame zu optimieren.
• Skalierbarkeit: Die Methode ermöglicht es, mehr Frames in das Modell einzuspeisen, ohne die Token-Anzahl zu erhöhen, was die Leistung bei langen Videos steigert.

4. Ergebnisse

Die Methode wurde auf zwei führenden Video-MLLMs (LLaVA-Video und LLaVA-OneVision) und fünf Benchmarks (u. a. VideoMME, MLVU, MVBench) evaluiert:

• Hohe Kompressionsraten: ForestPrune erreicht bei einer Token-Reduktion von 90 % eine durchschnittliche Genauigkeitserhaltung von 95,8 % (bei LLaVA-OneVision).
• Vergleich mit SOTA: Im Vergleich zu Methoden wie FrameFusion, G-Prune oder VisionZip zeigt ForestPrune bei hohen Kompressionsraten (90 %) signifikant bessere Ergebnisse.
  • Auf dem MLVU-Benchmark erzielte ForestPrune +10,1 % höhere Genauigkeit als FrameFusion.
  • Die Pruning-Zeit war um 81,4 % geringer als bei FrameFusion.
• Effizienz: ForestPrune reduziert nicht nur die GPU-Speichernutzung und die Rechenkomplexität (TFLOPS), sondern verkürzt auch die Vorverarbeitungszeit (Prefilling) erheblich, da die Kompression vor der Kodierung durch das MLLM erfolgt.
• Qualitative Analyse: Visualisierungen zeigen, dass ForestPrune bei Szenenwechseln neue Tokens hinzufügt und bei ähnlichen Szenen redundante Tokens entfernt, während bildbasierte Methoden oft redundante Frames beibehalten.

5. Bedeutung und Fazit

ForestPrune adressiert ein fundamentales Problem der Video-Verarbeitung in MLLMs: den Trade-off zwischen Recheneffizienz und der Bewahrung zeitlicher Informationen.

• Technischer Durchbruch: Es beweist, dass eine strukturierte, raum-zeitliche Modellierung (Wald-Struktur) überlegene Ergebnisse liefert als rein bildbasierte Ansätze.
• Praktische Relevanz: Die Methode ermöglicht den Einsatz von Video-MLLMs auf ressourcenbeschränkten Geräten oder für Echtzeitanwendungen, ohne dass die Modellleistung signifikant leidet.
• Zukunftsperspektive: Die Fähigkeit, durch Kompression mehr Frames pro Token-Budget zu verarbeiten, öffnet neue Wege für das Verständnis sehr langer Videos (Long-Video Understanding), was bisher ein Engpass war.

Zusammenfassend stellt ForestPrune einen neuen Standard für die effiziente Token-Kompression in Video-MLLMs dar, der durch seine innovative Wald-Struktur sowohl die Leistung als auch die Effizienz gegenüber dem State-of-the-Art deutlich verbessert.