🤖 machine learning

Budget Constraints as Riemannian Manifolds

Dit artikel stelt Riemanniaanse Beperkte Optimalisatie (RCO) voor, een nieuw raamwerk dat budgetbeperkingen modelleert als gladde Riemanniaanse variëteiten om efficiënte, op gradiënten gebaseerde optimalisatie van niet-decomposeerbare doelstellingen onder exacte budgethandhaving mogelijk te maken, en dat bestaande straf- en evolutionaire methoden overtreft in zowel oplossingskwaliteit als computationele efficiëntie voor taken zoals kwantisatie met gemengde precisie en het uitdunnen van experts.

Oorspronkelijke auteurs: Michael Helcig, Dan Alistarh

Gepubliceerd 2026-05-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Michael Helcig, Dan Alistarh

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de chef-kok bent van een enorm, high-end restaurant. Je hebt een strikt budget voor de avond, maar je hebt ook een menu met honderden gerechten, en elk gerecht kan op verschillende manieren worden bereid (bijvoorbeeld met premium ingrediënten, standaard ingrediënten of budgetvriendelijke vervangers).

Je doel is om precies één versie van elk gerecht te kiezen om te serveren, zodat de totale kosten exact binnen je budget blijven, terwijl je de totale kwaliteit van de maaltijd zo smakelijk mogelijk maakt.

Het probleem? De kwaliteit van de maaltijd is niet zomaar de som van de individuele gerechten. Als je een fancy biefstuk kiest, past die misschien beter bij een specifieke wijn, waardoor het 'smaakprofiel' van de hele tafel verandert. Dit maakt de wiskunde ontzettend moeilijk: je kunt niet naar elk gerecht op zichzelf kijken; je moet een gigantisch, verward puzzel oplossen waarbij elke keuze elke andere keuze beïnvloedt.

Dit is precies het probleem dat machine learning-engineers tegenkomen wanneer ze proberen enorme AI-modellen (zoals die chatbots aandrijven) te comprimeren. Ze moeten beslissen hoeveel ze verschillende onderdelen van het model moeten 'verkleinen' of 'wegsnijden' om binnen een groottebeperking (het budget) te blijven, zonder de intelligentie van het model (de kwaliteit) te verstoren.

Hier is hoe het artikel dit oplost, met behulp van een paar creatieve analogieën:

1. De Oude Manier: Gissen en Straffen

Voorheen probeerden ingenieurs twee hoofdmethoden, die allebei onhandig waren:

De "Straf"-methode: Ze vertelden de computer: "Probeer onder het budget te blijven, maar als je eroverheen gaat, krijg je een grote 'boete' (een strafscore)." Het probleem is dat de computer slecht is in het raden van de juiste boete. Als de boete te klein is, negeert hij het budget. Als hij te groot is, raakt de computer bang en stopt met leren. Het is alsof je een hond leert zitten door willekeurig op verschillende volumes "Nee!" te schreeuwen; de hond leert nooit de exacte regel.
De "Evolutionaire"-methode: Ze lieten de computer duizenden willekeurige combinaties proberen, hielden de beste vast en herhaalden dit. Dit werkt goed, maar is ontzettend traag. Het is alsof je probeert het beste recept te vinden door elke mogelijke maaltijd ter wereld te koken en ze één voor één te proeven. Het duurt eeuwen.

2. Het Nieuwe Idee: Het "Budget Manifold"

De auteurs realiseerden zich dat als je het probleem door een specifieke wiskundige lens bekijkt (met behulp van zoiets als "softmax"), de budgetbeperking geen rommelige muur is waar je tegenaan moet stuiteren. In plaats daarvan is het een glad, gebogen oppervlak (een manifold) waar je op kunt lopen.

Denk aan het budget niet als een harde omheining, maar als een luchtrek.

Het Oppervlak: Stel je een gigantisch, onzichtbaar, gebogen trampoline voor die alleen bestaat waar je totale kosten exact gelijk zijn aan je budget.
De Wandeltocht: De computer hoeft niet van de trampoline te springen en hopen dat hij er weer op landt. In plaats daarvan loopt hij langs het oppervlak.

3. Hoe de Nieuwe Methode (RCO) Werkt

Het artikel stelt een nieuw algoritme voor genaamd Riemannian Constrained Optimization (RCO). Zo beweegt het langs dat luchtrek:

Stap 1: De Tangentiestap (Vooruitlopen): De computer berekent de richting die de maaltijd smakelijker maakt (de gradiënt). Maar in plaats van gewoon die kant op te lopen, projecteert hij die richting op het oppervlak van het luchtrek. Dit zorgt ervoor dat hij nooit per ongeluk van de budgetlijn afstapt.
Stap 2: De Binair Zoeken (De Magische Glijbaan): Soms, zelfs als je voorzichtig loopt, drijf je iets van de lijn af. Bij andere methoden zou je een complexe berekening moeten doen om terug te komen. Hier vonden de auteurs een "magische glijbaan". Vanwege de specifieke wiskunde die ze gebruikten, kunnen ze het hele maaltijdplan gewoon omhoog of omlaag schuiven met één knop (een binaire zoektocht) om perfect terug te landen op de budgetlijn. Het is alsof je een afstandsbediening hebt die je evenwicht direct herstelt.
Stap 3: De Momentum (Het Ritme Behouden): Wanneer je over een gebogen oppervlak loopt, verandert je richting. Het algoritme heeft een speciale truc om zijn momentum (zijn geheugen van waar het naartoe ging) te "transporteren", zodat het niet duizelig wordt of zijn ritme verliest terwijl het langs de curve beweegt.

4. Waarom Het Een Groot Ding Is

Het artikel beweert dat deze methode een game-changer is om twee redenen:

Het is Exact: In tegenstelling tot de oude "straf"-methoden die vaak iets boven of onder het budget uitkomen, blijft deze methode bij elke enkele stap exact op de budgetlijn. Het is alsof een luchtrekloper die nooit wiebelt.
Het is Snel: Omdat het gradiënten (wiskundige richtingen) gebruikt in plaats van willekeurig gissen, vindt het de beste oplossing veel sneller.
- Het Resultaat: Bij tests met synthetische puzzels bleven de oude methoden steken op 83% van de best mogelijke score, terwijl deze nieuwe methode de perfecte oplossing vond.
- Realiteit: Toen ze het testten op het comprimeren van enorme AI-modellen (zoals het verkleinen van de grootte van een "Large Language Model"), kwam het overeen met of versloeg het de resultaten van de trage "evolutionaire" methoden, maar deed het dit 3 tot 16 keer sneller.

Samenvatting

Het artikel introduceert een nieuwe manier om "budget"-problemen in AI op te lossen. In plaats van het budget te behandelen als een harde limiet die je berekeningen breekt, hebben ze het omgezet in een glad, bewandelbaar oppervlak. Door langs dit oppervlak te lopen, kan de computer de perfecte balans tussen kosten en kwaliteit veel sneller en nauwkeuriger vinden dan voorheen, zonder dat er gegooid hoeft te worden of lastige instellingen hoeven te worden afgesteld. Het is het verschil tussen struikelen door een donkere kamer terwijl je probeert meubels te vermijden, en zelfverzekerd lopen over een goed verlicht, perfect geplaveid pad.

1. Probleemstelling

Het paper behandelt het budget-beperkte discrete toewijzingsprobleem, een terugkerende uitdaging in efficiënt machine learning. Het doel is om aan elke van $N$ groepen (bijvoorbeeld lagen van een neurale netwerken) één van $K$ discrete opties (bijvoorbeeld kwantisatie-bitbreedtes, pruning-beslissingen of selectie van experts) toe te wijzen om een globale doelstelling (bijvoorbeeld modelverlies) te minimaliseren, onderworpen aan een totale kostenbegroting (bijvoorbeeld modelgrootte of latentie).

Belangrijkste Uitdagingen:

Niet-decomposeerbaar Doelfunctie: Het modelverlies hangt gezamenlijk af van alle toewijzingen (bijvoorbeeld interacties tussen lagen), wat betekent dat het niet kan worden geschreven als een som van onafhankelijke termen per groep. Dit verhindert dat standaard Dynamisch Programmeren (DP) het werkelijke verlies direct optimaliseert; DP kan alleen "proxy"-doelfuncties optimaliseren (zoals gevoeligheid per laag).
Beperkingen van Bestaande Methoden:
- Combinatoire Oplossers (DP): Handhaven de begroting exact, maar vereisen decomposeerbare doelfuncties, waardoor het gebruik van onnauwkeurige proxy-scores noodzakelijk is.
- Evolutionair Zoeken: Evalueert het werkelijke verlies, maar mist gradiënten, vereist honderden forward passes en lijdt aan hoge rekenkosten.
- Straf/Lagrangiaanse Methoden: Voegen een strafterm toe (bijvoorbeeld $\lambda(C-B)^2$ ) aan het verlies. Deze handhaven de begroting slechts bij benadering, oscilleren vaak en vereisen gevoelige hyperparameter-tuning.

2. Methodologie: Riemanniaanse Beperkte Optimalisatie (RCO)

De auteurs stellen een geometrische aanpak voor door de budgetbeperking niet als een straf te behandelen, maar als een glad Riemanniaanse variëteit in de ruimte van logits.

A. De Budgetvariëteit

De auteurs parametriseren de toewijzingsverdeling voor elke groep $i$ met logits $\alpha_i \in \mathbb{R}^K$ , met kansen $p_i = \text{softmax}(\alpha_i)$ . De totale verwachte kosten worden gedefinieerd als:
$C(\alpha) = \sum_{i=1}^N w_i \langle p_i, c \rangle$
waarbij $w_i$ het groepsgewicht is en $c$ de kostenvector.

Variëteitsstructuur: Het niveauverzameling $\mathcal{M} = \{ \alpha \mid C(\alpha) = B \}$ is bewezen een gladde $(NK-1)$-dimensionale Riemanniaanse deelvariëteit te zijn.
Geometrische Eigenschappen:
1. Gesloten-vorm Normaal: De gradiënt $\nabla C(\alpha)$ is beschikbaar in gesloten vorm en is niet-nul (onder de aanname van onderscheiden kosten), wat de normaalvector tot de variëteit definieert.
2. Monotone Retractie: Het verschuiven van logits langs de kostenvector verandert de verwachte kosten monotoon. Dit stelt het algoritme in staat om elk punt terug te projecteren op de variëteit $\mathcal{M}$ met behulp van een eenvoudige binaire zoektocht (of Newton-methode) in plaats van complexe iteratieve projecties.
3. Goedkope Vectortransport: Het verplaatsen van momentum van het ene raakvlak naar het andere reduceert tot één inwendig product-operatie.

B. Het RCO-algoritme

Het voorgestelde algoritme omhult standaard optimalisatie van de eerste orde (Adam) met drie geometrische operaties om de begroting bij elke stap exact af te dwingen:

Raakprojectie: De verliesgradiënt wordt geprojecteerd op de raakruimte van de variëteit door de component langs de normaalvector $\nabla C(\alpha)$ te verwijderen. Dit zorgt ervoor dat de optimalisator alleen richtingen ziet die de begroting behouden.
Retractie: Na een Adam-stap kan de iteratie van de variëteit afdrijven. Het algoritme verschuift alle logits langs de kostenvector ( $\alpha' = \alpha + t \cdot c$ ) en gebruikt binaire zoektocht om $t$ te vinden zodat $C(\alpha') = B$ .
Momentumtransport: Het momentum van de optimalisator (eerste moment) wordt geprojecteerd op de nieuwe raakruimte om consistentie te behouden.

C. Omgaan met Discrete Haalbaarheid (Forward Pass)

Omdat de variëteit opereert in de continue logit-ruimte, combineert het paper RCO met:

Gumbel-STE (Straight-Through Estimator): Om discrete toewijzingen te genereren voor de forward pass.
Budget-beperkt Dynamisch Programmeren: Om het discrete toewijzingsprobleem (Multiple-Choice Knapsack Problem) exact op te lossen tijdens de forward pass, zodat de geëvalueerde configuratie voldoet aan de begroting.
Mechanisme: De forward pass gebruikt DP om de beste discrete configuratie $z^*$ te vinden gegeven verstoord logits. De backward pass gebruikt STE om gradiënten te laten stromen door de softmax-kansen van de verstoord logits, terwijl de variëteitsprojectie ervoor zorgt dat deze gradiënten de budgetbeperking niet schenden.

3. Belangrijkste Bijdragen

Identificatie van de Budgetvariëteit: De auteurs identificeren dat het niveauverzameling van softmax-verwachte kosten een Riemanniaanse variëteit vormt met unieke, rekenkundig goedkope geometrische eigenschappen (gesloten-vorm normalen, monotone retractie).
RCO-algoritme: Een nieuw optimalisatiekader dat exacte budgetbeperkingen afdwingt met nul constraint-hyperparameters (geen $\lambda$ om te tunen). Het combineert raakprojectie, binaire-zoektocht-retractie en momentumtransport rondom Adam.
Omgaan met Ongelijkheidbeperkingen: De variëteit wordt uitgebreid naar ongelijkheidsbeperkingen ( $C(\alpha) \le B$ ) via een slackvariabele $s$ , waardoor de optimalisator de ongebruikte begroting op natuurlijke wijze kan benutten zonder deze te verspillen aan inferieure opties.
Discrete-Continue Hybride: De integratie van Gumbel-STE en budget-beperkt DP maakt het mogelijk om het werkelijke niet-decomposeerbare modelverlies te optimaliseren terwijl exacte discrete haalbaarheid behouden blijft.

4. Experimentele Resultaten

Het paper valideert RCO op synthetische en real-world Large Language Model (LLM) compressietaken.

Synthetische Knapsack-problemen (MCKP):
- Op moeilijke instanties herstelt RCO de optimale oplossing van Dynamisch Programmeren (DP).
- Lagrangiaanse methoden plafonneren op 83% van de optimale waarde en vertonen significante beperkingsschendingen ( $10^{-1}$ tot $10^{-2}$ ), terwijl RCO schendingen handhaaft dicht bij machineprecisie ( $10^{-9}$ ).
- RCO behandelt "goedkope optimale" gevallen (waarbij de beste oplossing minder kost dan de begroting) perfect door gebruik te maken van de slackvariabele, terwijl gelijkheidsbeperkte methoden begroting verspillen.
MoE Expert Pruning:
- Geëvalueerd op OLMoE-1B-7B en Qwen3-30B-A3B.
- RCO komt overeen met of overtreft de nauwkeurigheid van EvoESAP (een evolutionair zoek-baseline) over meerdere benchmarks (ARC, MMLU, etc.).
- Efficiëntie: RCO bereikt deze resultaten in 3–16× lagere wandkloktijd (bijvoorbeeld ~10 minuten versus 5,8 uur voor EvoESAP).
Mixed-Precision Quantisatie:
- Geëvalueerd op Qwen3-8B (toewijzing van bitbreedtes 2–8 aan 252 lagen).
- Bij hoge compressie (2,25 bits) verlaagt RCO de perplexiteit met 36% vergeleken met HIGGS (een lineaire surrogate-methode) en met 4% vergeleken met EvoPress (evolutionair zoeken).
- RCO convergeert naar hetzelfde optimum als EvoPress bij 2,5 bits, maar in ~10× minder tijd (62 minuten versus 11–14 uur).

5. Betekenis en Impact

Exacte Handhaving van Beperkingen: In tegenstelling tot strafmethoden garandeert RCO dat de begroting bij elke iteratie exact wordt gehaald, waardoor de noodzaak voor hyperparameter-tuning van strafgewichten wordt geëlimineerd.
Optimalisatie van Niet-decomposeerbare Verliezen: Door de discrete haalbaarheid (afgehandeld door DP in de forward pass) te scheiden van de continue optimalisatie (afgehandeld door de variëteit in de backward pass), stelt RCO directe optimalisatie van complexe, niet-decomposeerbare modelverliezen (zoals end-to-end nauwkeurigheid) onder strikte budgetbeperkingen mogelijk.
Rekenkundige Efficiëntie: De geometrische operaties (projectie, retractie, transport) zijn rekenkundig goedkoop (essentieel inwendige producten en binaire zoektochten), waardoor de methode schaalbaar is voor grote modellen waar evolutionair zoeken onbetaalbaar duur is.
Generaliseerbaarheid: Het kader is toepasbaar op elk probleem dat softmax-parametrisatie met lineaire kosten omvat, en reikt verder dan modelcompressie tot resource-beperkte neurale architectuurzoek en andere discrete toewijzingsproblemen.

Samenvattend herformuleert het paper budget-beperkte discrete optimalisatie als een probleem van het navigeren door een specifieke Riemanniaanse variëteit, en biedt een theoretisch onderbouwde, hyperparameter-vrije en zeer efficiënt alternatief voor straf-gebaseerde en evolutionaire benaderingen.