🤖 machine learning

Budget Constraints as Riemannian Manifolds

Dieser Artikel stellt die Riemannsche restringierte Optimierung (RCO) vor, ein neuartiges Framework, das Budgetbeschränkungen als glatte Riemannsche Mannigfaltigkeiten modelliert, um eine effiziente, gradientenbasierte Optimierung nicht-dekomponierbarer Zielgrößen unter exakter Budgeteinhaltung zu ermöglichen und dabei sowohl in der Lösungsqualität als auch in der Recheneffizienz bestehende Straf- und evolutionäre Verfahren für Aufgaben wie die Quantisierung mit gemischter Genauigkeit und das Beschneiden von Experten übertrifft.

Ursprüngliche Autoren: Michael Helcig, Dan Alistarh

Veröffentlicht 2026-05-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Michael Helcig, Dan Alistarh

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind Küchenchef in einem riesigen, hochklassigen Restaurant. Sie haben ein striktes Budget für die Nacht, aber auch eine Speisekarte mit hunderten Gerichten, und jedes Gericht kann auf verschiedene Arten zubereitet werden (z. B. mit Premium-Zutaten, Standardzutaten oder preisgünstigen Ersatzprodukten).

Ihr Ziel ist es, genau eine Version jedes Gerichts auszuwählen, um sie zu servieren, sodass die Gesamtkosten exakt innerhalb Ihres Budgets bleiben, während Sie die Gesamtqualität des Mahls so lecker wie möglich machen.

Das Problem? Die Qualität des Mahls ist nicht einfach die Summe der einzelnen Gerichte. Wenn Sie ein edles Steak wählen, passt es möglicherweise besser zu einem bestimmten Wein, was das „Geschmacksprofil" des gesamten Tisches verändert. Das macht die Mathematik unglaublich schwierig: Sie können nicht einfach jedes Gericht isoliert betrachten; Sie müssen ein riesiges, verwickeltes Puzzle lösen, bei dem jede Wahl jede andere Wahl beeinflusst.

Dies ist exakt das Problem, mit dem Machine-Learning-Ingenieure konfrontiert sind, wenn sie versuchen, riesige KI-Modelle (wie die, die Chatbots antreiben) zu komprimieren. Sie müssen entscheiden, wie stark sie verschiedene Teile des Modells „verkleinern" oder „beschneiden", um ein Größenlimit (das Budget) einzuhalten, ohne die Intelligenz des Modells (die Qualität) zu ruinieren.

Hier ist, wie das Papier dieses Problem mit einigen kreativen Analogien löst:

1. Der alte Weg: Raten und Bestrafen

Früher versuchten Ingenieure zwei Hauptansätze, die beide ungeschickt waren:

Die „Straf"-Methode: Sie sagten dem Computer: „Versuche, unter dem Budget zu bleiben, aber wenn du darüber gehst, werde ich dir eine große 'Strafe' (ein Strafpunktwert) auferlegen." Das Problem ist, dass der Computer schlecht darin ist, die richtige Strafe zu erraten. Wenn die Strafe zu gering ist, ignoriert sie das Budget. Wenn sie zu hoch ist, bekommt der Computer Angst und hört auf zu lernen. Es ist wie der Versuch, einem Hund das Sitzen beizubringen, indem man in zufälligen Lautstärken „Nein!" schreit; der Hund lernt nie die genaue Regel.
Die „Evolutionäre" Methode: Sie ließen den Computer Tausende zufälliger Kombinationen ausprobieren, behielten die besten bei und wiederholten den Vorgang. Das funktioniert gut, ist aber unglaublich langsam. Es ist wie der Versuch, das beste Rezept zu finden, indem man jede mögliche Mahlzeit der Welt kocht und sie einzeln probiert. Es dauert ewig.

2. Die neue Idee: Das „Budget-Mannigfaltigkeits"-Konzept

Die Autoren erkannten, dass, wenn man das Problem durch eine bestimmte mathematische Linse betrachtet (unter Verwendung von etwas namens „Softmax"), die Budgetbeschränkung keine unordentliche Wand ist, an der man abprallen muss. Stattdessen ist es eine glatte, gekrümmte Oberfläche (eine Mannigfaltigkeit), auf der man laufen kann.

Denken Sie an das Budget nicht als harten Zaun, sondern als Seilbahn.

Die Oberfläche: Stellen Sie sich eine riesige, unsichtbare, gekrümmte Trampolinfläche vor, die nur dort existiert, wo Ihre Gesamtkosten exakt Ihrem Budget entsprechen.
Der Weg: Der Computer muss nicht vom Trampolin springen und hoffen, dass er wieder darauf landet. Stattdessen läuft er entlang der Oberfläche.

3. Wie die neue Methode (RCO) funktioniert

Das Papier schlägt einen neuen Algorithmus namens Riemannian Constrained Optimization (RCO) vor. So bewegt er sich entlang dieser Seilbahn:

Schritt 1: Der Tangential-Schritt (Vorwärtsgehen): Der Computer berechnet die Richtung, die das Mahl schmackhafter macht (den Gradienten). Aber anstatt einfach in diese Richtung zu gehen, projiziert er diese Richtung auf die Oberfläche der Seilbahn. Dies stellt sicher, dass er nie versehentlich von der Budgetlinie abkommt.
Schritt 2: Die Binärsuche (Die magische Rutsche): Manchmal, selbst wenn man vorsichtig läuft, driftet man leicht von der Linie ab. Bei anderen Methoden müsste man eine komplexe Berechnung durchführen, um zurückzukommen. Hier fanden die Autoren eine „magische Rutsche". Aufgrund der spezifischen Mathematik, die sie verwendeten, können sie den gesamten Mahlplan einfach an einem einzigen Regler (eine Binärsuche) nach oben oder unten schieben, um perfekt wieder auf der Budgetlinie zu landen. Es ist wie eine Fernbedienung, die Ihr Gleichgewicht sofort korrigiert.
Schritt 3: Der Impuls (Den Rhythmus beibehalten): Wenn Sie auf einer gekrümmten Oberfläche laufen, ändert sich Ihre Richtung. Der Algorithmus hat einen speziellen Trick, um seinen Impuls (seine Erinnerung daran, wohin er unterwegs war) zu „transportieren", damit er nicht schwindelig wird oder seinen Rhythmus verliert, während er sich entlang der Kurve bewegt.

4. Warum es eine große Sache ist

Das Papier behauptet, diese Methode sei aus zwei Gründen ein Game-Changer:

Sie ist exakt: Im Gegensatz zu den alten „Straf"-Methoden, die oft etwas über oder unter dem Budget landen, bleibt diese Methode bei jedem einzelnen Schritt exakt auf der Budgetlinie. Es ist wie ein Seiltänzer, der nie wackelt.
Sie ist schnell: Da sie Gradienten (mathematische Richtungen) anstelle von zufälligem Raten verwendet, findet sie die beste Lösung viel schneller.
- Das Ergebnis: Bei Tests mit synthetischen Puzzles blieben die alten Methoden bei 83 % der bestmöglichen Punktzahl stecken, während diese neue Methode die perfekte Lösung fand.
- Realwelt: Als sie es zum Komprimieren riesiger KI-Modelle testeten (z. B. beim Verkleinern der Größe eines „Large Language Model"), entsprach es den Ergebnissen der langsamen „evolutionären" Methoden oder übertraf sie, aber 3- bis 16-mal schneller.

Zusammenfassung

Das Papier stellt eine neue Art vor, „Budget"-Probleme in der KI zu lösen. Anstatt das Budget als harte Grenze zu behandeln, die Ihre Berechnungen zerstört, verwandelten sie es in eine glatte, begehbare Oberfläche. Indem sie entlang dieser Oberfläche laufen, kann der Computer viel schneller und genauer als zuvor das perfekte Gleichgewicht zwischen Kosten und Qualität finden, ohne knifflige Einstellungen raten oder anpassen zu müssen. Es ist der Unterschied zwischen dem Stolpern durch einen dunklen Raum, in dem man versucht, Möbel zu vermeiden, und dem selbstbewussten Gehen auf einem gut beleuchteten, perfekt gepflasterten Weg.

1. Problemstellung

Das Papier adressiert das budgetbeschränkte diskrete Zuordnungsproblem, eine wiederkehrende Herausforderung im effizienten maschinellen Lernen. Das Ziel ist es, jeder von $N$ Gruppen (z. B. Schichten eines neuronalen Netzwerks) eine von $K$ diskreten Optionen (z. B. Quantisierungs-Bitbreiten, Pruning-Entscheidungen oder Expertenauswahl) zuzuweisen, um ein globales Ziel (z. B. Modellverlust) unter Einhaltung eines Gesamtkostenbudgets (z. B. Modellgröße oder Latenz) zu minimieren.

Herausforderungen:

Nicht-dekomponierbares Ziel: Der Modellverlust hängt gemeinsam von allen Zuweisungen ab (z. B. Interaktionen zwischen Schichten), was bedeutet, dass er nicht als Summe unabhängiger pro-Gruppen-Terme geschrieben werden kann. Dies verhindert, dass Standard-Dynamische Programmierung (DP) den tatsächlichen Verlust direkt optimiert; DP kann nur „Proxy"-Ziele (wie schichtweise Sensitivität) optimieren.
Einschränkungen bestehender Methoden:
- Kombinatorische Löser (DP): Behandeln das Budget exakt, erfordern jedoch dekomponierbare Ziele, was die Verwendung ungenauer Proxy-Scores erzwingt.
- Evolutionäre Suche: Bewertet den tatsächlichen Verlust, fehlt es jedoch an Gradienten, erfordert hunderte Vorwärtsdurchläufe und leidet unter hohen Rechenkosten.
- Straf-/Lagrange-Methoden: Fügen einen Strafterm (z. B. $\lambda(C-B)^2$ ) zum Verlust hinzu. Diese setzen das Budget nur näherungsweise durch, oszillieren häufig und erfordern eine empfindliche Hyperparameter-Abstimmung.

2. Methodik: Riemannische restringierte Optimierung (RCO)

Die Autoren schlagen einen geometrischen Ansatz vor, bei dem die Budgetbeschränkung nicht als Strafe, sondern als glatte Riemannsche Mannigfaltigkeit im Raum der Logits behandelt wird.

A. Die Budget-Mannigfaltigkeit

Die Autoren parametrisieren die Zuordnungsverteilung für jede Gruppe $i$ mittels Logits $\alpha_i \in \mathbb{R}^K$ , mit Wahrscheinlichkeiten $p_i = \text{softmax}(\alpha_i)$ . Die erwarteten Gesamtkosten sind definiert als:
$C(\alpha) = \sum_{i=1}^N w_i \langle p_i, c \rangle$
wobei $w_i$ das Gruppenweight und $c$ der Kostenvektor ist.

Mannigfaltigkeitsstruktur: Das Niveaulinie $\mathcal{M} = \{ \alpha \mid C(\alpha) = B \}$ wird als glatte $(NK-1)$-dimensionale Riemannsche Untermannigfaltigkeit nachgewiesen.
Geometrische Eigenschaften:
1. Geschlossene Form des Normalenvektors: Der Gradient $\nabla C(\alpha)$ ist in geschlossener Form verfügbar und ungleich null (unter der Annahme unterschiedlicher Kosten), was den Normalenvektor zur Mannigfaltigkeit definiert.
2. Monotone Retraktion: Das Verschieben von Logits entlang des Kostenvektors ändert die erwarteten Kosten monoton. Dies ermöglicht es dem Algorithmus, jeden Punkt zurück auf die Mannigfaltigkeit $\mathcal{M}$ zu projizieren, indem eine einfache binäre Suche (oder Newton-Verfahren) anstelle komplexer iterativer Projektionen verwendet wird.
3. Günstiger Vetransport: Das Bewegen von Momentum von einer Tangentialebene zur anderen reduziert sich auf eine einzige Skalarprodukt-Operation.

B. Der RCO-Algorithmus

Der vorgeschlagene Algorithmus umhüllt Standard-Optimierung erster Ordnung (Adam) mit drei geometrischen Operationen, um das Budget in jedem Schritt exakt einzuhalten:

Tangentiale Projektion: Der Verlustgradient wird auf den Tangentialraum der Mannigfaltigkeit projiziert, indem die Komponente entlang des Normalenvektors $\nabla C(\alpha)$ entfernt wird. Dies stellt sicher, dass der Optimierer nur Richtungen sieht, die das Budget erhalten.
Retraktion: Nach einem Adam-Schritt kann die Iterierte von der Mannigfaltigkeit abweichen. Der Algorithmus verschiebt alle Logits entlang des Kostenvektors ( $\alpha' = \alpha + t \cdot c$ ) und verwendet eine binäre Suche, um $t$ zu finden, sodass $C(\alpha') = B$ gilt.
Momentum-Transport: Das Momentum (erster Moment) des Optimierers wird auf den neuen Tangentialraum projiziert, um Konsistenz zu gewährleisten.

C. Behandlung diskreter Machbarkeit (Vorwärtsdurchlauf)

Da die Mannigfaltigkeit im kontinuierlichen Logit-Raum operiert, kombiniert das Papier RCO mit:

Gumbel-STE (Straight-Through Estimator): Zur Generierung diskreter Zuweisungen für den Vorwärtsdurchlauf.
Budgetbeschränkter Dynamischer Programmierung: Zur exakten Lösung des diskreten Zuordnungsproblems (Multiple-Choice-Knapsack-Problem) während des Vorwärtsdurchlaufs, um sicherzustellen, dass die bewertete Konfiguration das Budget einhält.
Mechanismus: Der Vorwärtsdurchlauf verwendet DP, um die beste diskrete Konfiguration $z^*$ unter Berücksichtigung gestörter Logits zu finden. Der Rückwärtsdurchlauf nutzt STE, um Gradienten durch die Softmax-Wahrscheinlichkeiten der gestörten Logits zu leiten, während die Mannigfaltigkeitsprojektion sicherstellt, dass diese Gradienten die Budgetbeschränkung nicht verletzen.

3. Hauptbeiträge

Identifikation der Budget-Mannigfaltigkeit: Die Autoren identifizieren, dass die Niveaulinie der Softmax-erwarteten Kosten eine Riemannsche Mannigfaltigkeit mit einzigartigen, rechnerisch günstigen geometrischen Eigenschaften bildet (geschlossene Normalenvektoren, monotone Retraktion).
RCO-Algorithmus: Ein neuartiges Optimierungsframework, das exakte Budgetbeschränkungen mit null Constraint-Hyperparametern durchsetzt (kein $\lambda$ zum Abstimmen). Es kombiniert tangentiale Projektion, Retraktion mittels binärer Suche und Momentum-Transport um Adam herum.
Behandlung von Ungleichheitsbeschränkungen: Die Mannigfaltigkeit wird auf Ungleichheitsbeschränkungen ( $C(\alpha) \le B$ ) über eine Schlupfvariable $s$ erweitert, was dem Optimierer ermöglicht, ungenutztes Budget natürlich zu nutzen, ohne es auf untergeordnete Optionen zu verschwenden.
Hybrid aus Diskret und Kontinuierlich: Die Integration von Gumbel-STE und budgetbeschränkter DP ermöglicht die Optimierung des tatsächlichen nicht-dekomponierbaren Modellverlusts bei gleichzeitiger Aufrechterhaltung exakter diskreter Machbarkeit.

4. Experimentelle Ergebnisse

Das Papier validiert RCO an synthetischen und realweltlichen Large Language Model (LLM)-Komprimierungsaufgaben.

Synthetische Knapsack-Probleme (MCKP):
- Bei schwierigen Instanzen stellt RCO die optimale Lösung der Dynamischen Programmierung (DP) wieder her.
- Lagrange-Methoden stagnieren bei 83% des optimalen Werts und zeigen signifikante Verletzungen der Beschränkungen ( $10^{-1}$ bis $10^{-2}$ ), während RCO Verletzungen nahe der Maschinengenauigkeit ( $10^{-9}$ ) beibehält.
- RCO behandelt „günstige optimale" Fälle (wo die beste Lösung weniger als das Budget kostet) perfekt durch Nutzung der Schlupfvariable, während gleichheitsbeschränkte Methoden Budget verschwenden.
MoE-Expert-Pruning:
- Evaluiert an OLMoE-1B-7B und Qwen3-30B-A3B.
- RCO erreicht oder übertrifft die Genauigkeit von EvoESAP (eine evolutionäre Such-Baseline) über mehrere Benchmarks (ARC, MMLU, etc.).
- Effizienz: RCO erzielt diese Ergebnisse in 3–16× geringerer Wandzeit (z. B. ~10 Minuten vs. 5,8 Stunden für EvoESAP).
Gemischt-Präzisions-Quantisierung:
- Evaluiert an Qwen3-8B (Zuweisung von Bitbreiten 2–8 an 252 Schichten).
- Bei hoher Kompression (2,25 Bits) reduziert RCO die Perplexität um 36% im Vergleich zu HIGGS (eine lineare Surrogat-Methode) und um 4% im Vergleich zu EvoPress (evolutionäre Suche).
- RCO konvergiert bei 2,5 Bits zum selben Optimum wie EvoPress, jedoch in ~10× weniger Zeit (62 Minuten vs. 11–14 Stunden).

5. Bedeutung und Auswirkung

Exakte Durchsetzung von Beschränkungen: Im Gegensatz zu Strafmethoden garantiert RCO, dass das Budget in jedem Iterationsschritt exakt eingehalten wird, wodurch die Notwendigkeit einer Hyperparameter-Abstimmung von Strafgewichten entfällt.
Optimierung nicht-dekomponierbarer Verluste: Durch die Trennung der diskreten Machbarkeit (behandelt durch DP im Vorwärtsdurchlauf) von der kontinuierlichen Optimierung (behandelt durch die Mannigfaltigkeit im Rückwärtsdurchlauf) ermöglicht RCO die direkte Optimierung komplexer, nicht-dekomponierbarer Modellverluste (wie End-to-End-Genauigkeit) unter strengen Budgetbeschränkungen.
Rechnerische Effizienz: Die geometrischen Operationen (Projektion, Retraktion, Transport) sind rechnerisch günstig (im Wesentlichen Skalarprodukte und binäre Suchen), was die Methode auf große Modelle skalierbar macht, bei denen evolutionäre Suche prohibitiv teuer ist.
Generalisierbarkeit: Das Framework ist auf jedes Problem anwendbar, das eine Softmax-Parametrisierung mit linearen Kosten beinhaltet, und geht über die Modellkomprimierung hinaus hin zu ressourcenbeschränkter neuronaler Architektursuche und anderen diskreten Zuordnungsproblemen.

Zusammenfassend stellt das Papier die budgetbeschränkte diskrete Optimierung als Problem der Navigation auf einer spezifischen Riemannschen Mannigfaltigkeit neu dar und bietet eine theoretisch fundierte, hyperparameterfreie und hocheffiziente Alternative zu strafbasierten und evolutionären Ansätzen.