Rechnerische Herausforderungen und Fortschritte bei Visuellen Autoregressiven Modellen

Visuelle Autoregressive Modelle (VAR): Ein Blick auf die rechnerischen Grenzen Visuelle Generierungsmodelle haben in den letzten Jahren enorme Fortschritte gemacht und finden Anwendung in Bereichen wie Bildverbesserung, Augmented Reality, medizinischer Diagnostik und kreativen Bereichen. Methoden wie Variationsautoencoder (VAE), Generative Adversarial Networks (GAN) und Diffusionsmodelle haben die Möglichkeiten der visuellen Generierung erweitert und die Realitätsnähe, Diversität und Gesamtqualität der erzeugten Bilder verbessert. VAR-Modelle stellen einen Paradigmenwechsel in der Bildgenerierung dar. Anstelle der herkömmlichen "Next-Token-Vorhersage" verwenden sie ein "Next-Scale-Prediction"-Verfahren, das von grob zu fein arbeitet. Dies ermöglicht autoregressiven Transformatoren, visuelle Verteilungen effizienter zu lernen und diffusionsbasierte Alternativen zu übertreffen. Darüber hinaus zeigen VAR-Modelle robuste Zero-Shot-Fähigkeiten bei Aufgaben wie Bildinpainting und -bearbeitung. Trotz ihrer Stärken besteht Bedarf an der Untersuchung der rechnerischen Grenzen von VAR-Modellen und der Entwicklung effizienter Algorithmen. Während VAR-Modelle die Komplexität von O(n⁶) früherer autoregressiver Methoden auf O(n⁴) reduzieren, wobei n die Höhe und Breite der letzten VQ-Code-Map ist, stellt diese Rechenzeit weiterhin eine Herausforderung dar. Diese Untersuchung konzentriert sich auf die Frage, ob die Berechnungen von VAR-Modellen schneller als in O(n⁴) durchgeführt werden können. Die wichtigsten Ergebnisse dieser Analyse lassen sich wie folgt zusammenfassen: Rechnerische Grenzen: Die Analyse der VAR-Modelle unter der Strong Exponential Time Hypothesis (SETH) zeigt, dass eine entscheidende Grenze für die Norm der Eingabematrizen für Aufmerksamkeitsberechnungen existiert. R bezeichnet die obere Schranke der Elemente in diesen Matrizen. Es wurde ein Kriterium R* = Θ(log⁡n) ermittelt. Nur wenn R unter diesem Schwellenwert liegt, können VAR-Modelle in einer Zeit von O(n⁴⁻ᵝ) (echte sub-quartische Zeit) berechnet werden. Nachweislich effiziente Kriterien: Wenn R = o(log⁡n) ist, kann ein Algorithmus entwickelt werden, der das VAR-Modell in nahezu quadratischer Zeit, genauer gesagt O(n²⁺ᵒ⁽¹⁾), approximiert. Das erste Ergebnis zeigt, dass bei R ≥ Ω(log⁡n) kein echter sub-quartischer Zeit-Algorithmus möglich ist. Dieses Ergebnis basiert auf der SETH, einer Hypothese aus der feinkörnigen Komplexitätstheorie, die die Zeit für die Lösung von k-SAT-Problemen betrifft. Satz (Rechnerische Grenzen von VAR-Modellen): Angenommen, d = O(log⁡n) und R = Θ(log⁡n). Unter der Annahme von SETH gibt es keinen Algorithmus, der das VAR-Modell mit einem additiven Fehler von 1/poly(n) in O(n⁴⁻ᵝ) Zeit approximiert. Das zweite Ergebnis zeigt, dass bei R = o(log⁡n) ein nahezu quadratischer Zeit-Algorithmus existiert. Satz (Existenz eines nahezu quadratischen Zeit-Algorithmus): Angenommen, d = O(log⁡n) und R = o(log⁡n). Es gibt einen Algorithmus, der das VAR-Modell mit einem additiven Fehler von 1/poly(n) in O(n²⁺ᵒ⁽¹⁾) Zeit approximiert. Diese Arbeit leistet einen Beitrag zum Verständnis der rechnerischen Effizienz von VAR-Modellen. Die Ergebnisse bieten Anhaltspunkte für die Entwicklung skalierbarer und effizienter Bildgenerierungsverfahren im Rahmen von VAR. Bibliographie: https://www.arxiv.org/abs/2501.04377 https://arxiv.org/html/2501.04377v1 https://paperreading.club/page?id=277279 https://openreview.net/pdf?id=vXUqOCsbj8 https://icml.cc/virtual/2024/calendar https://nips.cc/virtual/2024/papers.html https://openreview.net/pdf/f644fc28533c9468770504bbf37df8471d9b8391.pdf https://icml.cc/Downloads/2024 https://jmlr.org/tmlr/papers/ https://mcml.ai/publications/