🤖 machine learning

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

Diese Arbeit zeigt, dass selbst eine minimale Überparametrisierung in Schwellwertschaltungen und Logarithmus-Präzision-Transformern eine exakte und approximative Zertifizierung exponentiell schwierig machen kann, eine theoretische Barriere, die empirisch durch die Schwierigkeit validiert wird, Fehler in trainierten Modellen zu erkennen, die eine binäre Addition durchführen.

Ursprüngliche Autoren: Artur Back de Luca, Kimon Fountoulakis

Veröffentlicht 2026-05-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Artur Back de Luca, Kimon Fountoulakis

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 eine Lehrkraft, die überprüfen möchte, ob eine Schülerin oder ein Schüler eine bestimmte mathematische Regel wirklich verstanden hat, wie etwa „wie man zwei Zahlen addiert". Sie haben eine Liste von Beispielen (Eingabe-Ausgabe-Paare) und möchten zu 100 % sicher sein, dass die Schülerin oder der Schüler nicht nur rät oder einem Trick folgt.

Diese Arbeit stellt eine fundamentale Frage: Wie viele Beispiele müssen Sie einer Schülerin oder einem Schüler zeigen, um nachzuweisen, dass sie oder er die exakte Regel kennt und nicht nur eine sehr ähnliche?

Die Autoren, Artur Back de Luca und Kimon Fountoulakis, entdeckten eine überraschende und etwas beunruhigende Wahrheit: Selbst eine winzige, fast unsichtbare Veränderung im „Gehirn" (dem Modell) der Schülerin oder des Schülers kann es unmöglich machen, zu beweisen, dass sie oder er korrekt ist, egal wie viele Beispiele Sie ihnen zeigen.

Hier ist die Aufschlüsselung ihrer Erkenntnisse mit einfachen Analogien:

1. Das „Betrüger"-Problem

Stellen Sie sich vor, Sie haben eine perfekte Schülerin oder einen perfekten Schüler, die oder der die Regel für das Addieren von Zahlen kennt. Sie wollen beweisen, dass sie oder er der einzige ist, der sie kennt.

Das einfache Szenario: Wenn die Schülerin oder der Schüler die einzige Person im Raum ist, benötigen Sie möglicherweise nur 5 oder 10 Beispiele, um zu beweisen, dass sie oder er die Regel kennt.
Das schwierige Szenario: Stellen Sie sich nun vor, Sie laden 1.000 „Betrüger" in den Raum ein. Diese Betrüger sind fast perfekt. Sie erhalten die Antwort in 99,9 % der Fälle richtig. Der einzige Fehler tritt bei einem sehr spezifischen, versteckten Satz von Zahlen auf (wie Zahlen, die mit der Ziffer „7" beginnen).

Die Arbeit zeigt, dass Sie, wenn Sie nur ein zusätzliches „Neuron" (ein winziges bisschen zusätzliche Rechenkraft) zu einem Modell hinzufügen, Millionen dieser Betrüger erzeugen können. Jeder Betrüger stimmt mit dem perfekten Schüler in fast allem überein, aber sie alle weichen bei einem anderen, winzigen, versteckten Satz von Zahlen ab.

2. Die Analogie „Nadel im Heuhaufen"

Um zu beweisen, dass der Schüler der echte ist und kein Betrüger, müssen Sie die spezifische Zahl finden, bei der sie oder er abweicht.

Wenn Sie 1.000 Betrüger haben und jeder seinen Fehler in einer anderen, winzigen Ecke des Universums der Zahlen versteckt, müssen Sie jede einzelne Ecke überprüfen, um sicherzugehen.
Die Arbeit beweist, dass, wenn Sie nur ein zusätzliches Gatter zu einem Schaltkreis hinzufügen (oder einen zusätzlichen „Attention Head" zu einer Transformer-KI), die Anzahl dieser versteckten Ecken explodiert.
Das Ergebnis: Um alle Betrüger zu fangen, müssen Sie möglicherweise Milliarden von Beispielen überprüfen. Wenn Sie nur einige Tausend überprüfen (eine „polynomielle" Anzahl), werden Sie die Betrüger wahrscheinlich übersehen, und der Schüler besteht Ihren Test, obwohl er oder sie tatsächlich falsch liegt.

3. Die zwei Hauptcharaktere

Die Autoren testeten dies an zwei Arten von „Schülern":

Schaltkreise: Denken Sie an diese als einfache, starre Logikmaschinen (wie ein Taschenrechner). Sie stellten fest, dass das Hinzufügen von nur einem zusätzlichen Schalter zu einem Schaltkreis der Tiefe 2 oder mehr es exponentiell schwieriger macht, die Antwort zu zertifizieren.
Transformer: Dies sind die leistungsstarken KI-Modelle hinter Tools wie Chatbots. Die Autoren zeigten, dass das Hinzufügen von nur einem zusätzlichen Attention Head (eine winzige architektonische Anpassung) und ein paar zusätzlichen Zahlen zum Speicher des Modells es unmöglich macht, dies mit einer vernünftigen Anzahl von Beispielen zu zertifizieren.

4. Die Falle der „fast perfekten" Leistung

Sie könnten denken: „Okay, aber was ist, wenn wir einfach akzeptieren, dass die Schülerin oder der Schüler ein paar Fehler macht? Was ist, wenn wir sagen: 'Wenn sie oder er 99 % richtig hat, ist das gut genug'?"
Die Arbeit sagt: Seien Sie vorsichtig.

Absolute Fehler: Wenn Sie sagen: „Sie dürfen insgesamt nur 10 Fehler machen", verstecken sich die Betrüger trotzdem. Sie benötigen immer noch Milliarden von Beispielen, um diese 10 Fehler zu finden, da sie über Milliarden von Möglichkeiten verstreut sind.
Relative Fehler: Wenn Sie sagen: „Sie dürfen 1 % Fehler machen", können die Betrüger Millionen von Fehlern verstecken, solange dieser 1 % klein genug ist. Das Modell kann in absoluten Zahlen völlig falsch liegen und trotzdem Ihren „99 % Genauigkeit"-Test bestehen.

5. Das Realwelt-Experiment

Um zu beweisen, dass dies nicht nur Mathematiktheorie ist, bauten sie diese Modelle tatsächlich:

Das Schaltkreis-Experiment: Sie bauten einen Schaltkreis, der Zahlen addiert, und schufen dann Tausende von „defekten" Versionen, die nur bei bestimmten Eingaben versagen. Sie zeigten, dass selbst bei einer riesigen Anzahl von Testbeispielen viele dieser defekten Schaltkreise immer noch perfekt aussahen.
Das Transformer-Experiment: Sie trainierten KI-Modelle, um Zahlen zu addieren. Selbst nachdem sie sie so lange trainiert hatten, dass sie strenge Validierungstests bestanden (99,9 % richtig), stellten sie fest, dass einige Modelle immer noch versteckte Fehler hatten. Als sie versuchten, diese Modelle mit zufälligen Beispielen zu „auditieren", bestanden die Modelle den Test weiterhin, obwohl sie eigentlich nicht perfekt waren.

Das Fazit

Die Arbeit kommt zu dem Schluss, dass Zertifizierung extrem zerbrechlich ist.
Wenn Sie garantieren wollen, dass eine KI oder ein Schaltkreis genau das tut, was Sie denken, dass sie oder er tut, können Sie sich nicht auf die durchschnittliche Leistung verlassen. Wenn das Modell auch nur ein winziges bisschen „zusätzliche Kapazität" hat (Überparametrisierung), kann es eine exponentielle Anzahl von Möglichkeiten verbergen, falsch zu liegen.

Um wirklich sicher zu sein, müssten Sie das Modell möglicherweise an einer so großen Anzahl von Beispielen testen, dass dies in der Praxis unmöglich wird. Es ist wie der Versuch, zu beweisen, dass ein Magier nicht betrügt, indem man ihm ein paar Mal eine Trickvorführung zuschaut; wenn er eine geheime zusätzliche Karte im Ärmel hat, werden Sie diese vielleicht nie sehen, es sei denn, Sie überprüfen jede einzelne Karte im Deck.

Technische Zusammenfassung: Zertifizierung aus Beispielen ist für Schaltkreise und Transformer unter minimaler Überparametrisierung schwierig

Problemstellung

Da state-of-the-art neuronale Netze zunehmend für Schlussfolgerungs- und algorithmische Aufgaben eingesetzt werden, wird die Sicherstellung ihrer exakten Korrektheit kritisch. Hohe Genauigkeit im Durchschnittsfall verdeckt oft inkonsistentes Verhalten, was die Erkennung von Fehlern erschwert, die von der beabsichtigten Schlussfolgerungslogik abweichen. Dieser Beitrag adressiert das Problem der exakten Zertifizierung: die Bestimmung der minimalen Anzahl an gelabelten Eingabe-Ausgabe-Beispielen, die erforderlich ist, um eine Zielfunktion $f^*$ innerhalb einer Hypothesenklasse $\mathcal{H}$ eindeutig zu identifizieren, sodass keine andere Hypothese in $\mathcal{H}$ mit $f^*$ auf dem gesamten Definitionsbereich übereinstimmt.

Die zentrale Frage lautet, wie empfindlich diese Zertifizierungskomplexität auf die Größe der umgebenden Hypothesenklasse reagiert. Konkret untersuchen die Autoren, ob eine minimale Vergrößerung der Hypothesenklasse (z. B. das Hinzufügen eines einzelnen Gatters oder einer konstanten Anzahl von Parametern) die Zertifizierung selbst für Ziele, die zuvor einfach zu zertifizieren waren, exponentiell schwieriger machen kann.

Methodik

Der Beitrag nutzt einen theoretischen Rahmen, der in der Lehrkomplexität und der Schaltkreiskomplexität verwurzelt ist, ergänzt durch eine empirische Validierung an Aufgaben zur binären Addition.

Theoretischer Rahmen

Definition der Zertifizierungsgröße: Die Autoren definieren die Zertifizierungsgröße, $\text{cert}(f^*, \mathcal{H})$ , als die minimale Größe einer gelabelten Stichprobe $S$ , sodass der Versionsraum $V_S^{\mathcal{H}}$ (die Menge der Hypothesen in $\mathcal{H}$ , die mit $S$ konsistent sind) nur $f^*$ enthält.
Prinzip der disjunkten Meinungsverschiedenheit: Die zentrale Beweisstrategie beruht auf der Konstruktion einer Menge von „Täusch"-Hypothesen. Für ein Ziel $f^*$ $f^{*}$ konstruieren die Autoren eine Familie von Hypothesen $\{g_\pi\}$ ${g_{π}}$ , die mit $f^*$ $f^{*}$ überall übereinstimmen, außer auf spezifischen, paarweise disjunkten „Auslöser-Blöcken" $B_\pi$ $B_{π}$ .
- Enthält eine Hypothesenklasse eine solche Familie von Täuschern, bei denen die Mengen der Meinungsverschiedenheiten disjunkt sind, muss jede exakte Zertifizierung mindestens ein Beispiel aus jeder Menge der Meinungsverschiedenheit enthalten.
- Folglich ist die Zertifizierungsgröße durch die Anzahl solcher disjunkten Blöcke nach unten beschränkt.
Analyse der Überparametrisierung: Die Autoren analysieren, wie das Hinzufügen minimaler Kapazität (z. B. ein zusätzliches Gatter in Schaltkreisen, ein zusätzlicher Attention-Kopf und eine konstante Embedding-Breite in Transformer) die Konstruktion dieser exponentiellen Familien von Täuschern für jedes Ziel in der ursprünglichen, kleineren Klasse ermöglicht.

Empirische Analyse

Die Autoren ergänzen die Theorie durch zwei Experimente zur Erkennung binärer Addition:

Konstruierte Schaltkreise: Sie setzen die theoretische Konstruktion von Täuschern für Schwellwertschaltkreise ( $TC_0$ ) zur Erkennung von Addition um. Sie generieren eine Menge von $2^n$ fehlerhaften Schaltkreisen, die sich jeweils in einem distincten Block von Eingaben vom Ziel unterscheiden, und messen, wie viele von ihnen bei einer uniformen Stichprobe von Zertifizierungskandidaten überleben.
Trainierte Transformer: Sie trainieren Encoder-only-Transformer auf 10-Bit-Addition. Nach der Auswahl von Modellen, die strenge Validierungsprüfungen bestehen (99,9 % Genauigkeit), evaluieren sie diese auf einem großen zurückgehaltenen Testset. Sie analysieren das „Überleben" dieser unvollkommenen Modelle (Täuscher), wenn sie uniformen Stichproben von Zertifizierungskandidaten ausgesetzt werden, und testen, ob Restfehler mit polynomial großem Stichprobenumfang erkannt werden können.

Wichtige Beiträge und Ergebnisse

1. Exponentielle Härte durch minimale Überparametrisierung

Der primäre theoretische Beitrag besteht darin zu zeigen, dass die Zertifizierung hochgradig empfindlich auf die Größe der Hypothesenklasse reagiert.

Schwellwertschaltkreise ( $TC_0$ ): Für Schaltkreise mit Tiefe $d \ge 2$ zwingt das Hinzufügen eines einzigen zusätzlichen Schwellwertgatters (Erhöhung des Gatterbudgets von $s$ auf $s+1$ ) die Zertifizierungsgröße für jedes Ziel in der ursprünglichen Klasse $TC_{d,s}$ dazu, exponentiell in der Eingabedimension $n$ zu werden. Konkret gilt: $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ .
Transformer: Für Transformer mit logarithmischer Genauigkeit und hard attention mit Mittelwertbildung (AHAT) erzeugt das Hinzufügen von einem Attention-Kopf in der letzten Schicht und sechs zusätzlichen Embedding-/Residual-Koordinaten eine vergrößerte Klasse, in der die Zertifizierung exponentiell schwierig wird. Selbst wenn ein Ziel $f^*$ in der kleineren Architektur eine polynomial große Zertifizierung besitzt, erfordert es eine exponentielle Anzahl von Beispielen, um es gegen die leicht größere Architektur zu zertifizieren.
Nicht-Vakuität: Die Autoren beweisen, dass diese unteren Schranken nicht vakant sind. Sie zeigen, dass die kleineren Klassen ( $TC_{d,s}$ und Standard-Transformer) Ziele mit polynomialer Zertifizierungsgröße enthalten (speziell $O(\log |\mathcal{H}|)$ ), doch diese gleichen Ziele werden exponentiell schwer zu zertifizieren, sobald die Klasse minimal vergrößert wird.

2. Härte der approximativen Zertifizierung

Der Beitrag erweitert diese Ergebnisse auf die approximative Zertifizierung:

Absolute Fehlertoleranz: Wenn die Zertifizierung nur eine polynomial große Anzahl von Fehlern zulässt ( $R = \text{poly}(n)$ ), bleibt die Zertifizierungsgröße exponentiell ( $2^{\Omega(n)}$ ).
Relative Fehlertoleranz: Wenn die Zertifizierung einen konstanten relativen Fehler ( $\epsilon$ ) zulässt, kann die Zertifizierungsgröße klein sein (polynomial in $1/\epsilon$ ). Dies geht jedoch zu Lasten des Zulassens exponentiell vieler absoluter Fehler. Die Autoren zeigen, dass Garantien für konstante relative Fehler exponentiell viele Fehler verbergen können, während Garantien für polynomialen absoluten Fehler dennoch exponentielle Zertifizierungen erfordern.

3. Empirische Validierung

Schaltkreis-Experimente: Die konstruierten $TC_0$ -Täuscher bestätigten die theoretische Barriere. Selbst bei polynomial großem Zertifizierungskandidaten blieben fast alle konstruierten Täuscher mit den gelabelten Stichproben konsistent, was eine exponentielle Stichprobennahme zur Eliminierung erforderte.
Transformer-Experimente: Unter 150 trainierten Modellen, die umfangreiche Validierungen bestanden, wiesen 63 Restfehler auf dem zurückgehaltenen Testset auf. Die Analyse zeigte, dass selbst mit einer gezielten Teilmenge von fehlerreichen Beispielen uniform gestochene Zertifizierungskandidaten polynomialer Größe versagten, alle nicht-exakten Hypothesen zu eliminieren. Unvollkommene Modelle konnten sich der Erkennung durch große, uniform gestochene Kandidaten entziehen.

Bedeutung und Behauptungen

Der Beitrag beansprucht, eine quantitative Form der Zertifizierungshärte für das exakte Lernen bereitzustellen. Seine Bedeutung liegt in folgenden Aussagen:

Empfindlichkeit gegenüber der Modellkapazität: Zertifizierung ist nicht lediglich eine Eigenschaft der Zielfunktion, sondern hängt kritisch von der „umgebenden" Hypothesenklasse ab. Eine minimale Erhöhung der Modellkapazität (konstanter Overhead) kann die Schwierigkeit der Verifizierung der Korrektheit eines Modells grundlegend verändern.
Grenzen der passiven Zertifizierung: In passiven Settings (bei denen Beispiele ohne Abfrage des Modells gestochen werden) sind polynomial große Datensätze unzureichend, um zu zertifizieren, dass ein Modell die beabsichtigte Berechnung gelernt hat, wenn die Hypothesenklasse leicht überparametrisiert ist.
Unterscheidung von Lernbarkeit: Die Ergebnisse heben eine Lücke zwischen Lernbarkeit und Zertifizierung hervor. Während eine Funktion lernbar sein mag (oder eine kleine Zertifizierung in einer eingeschränkten Klasse besitzt), kann ihre Zertifizierung gegen eine leicht größere Klasse unlösbar sein.
Implikationen für Schlussfolgerungsmodelle: Für Modelle, die auf algorithmischen Aufgaben (wie Addition) eingesetzt werden, garantiert hohe Validierungsgenauigkeit keine Exaktheit. Der Beitrag legt nahe, dass ohne stärkere Protokolle (z. B. aktives Lernen oder spezifische Abfragen) große, uniform gestochene Datensätze möglicherweise subtile, strukturierte Inkonsistenzen in Schlussfolgerungsmodellen nicht erkennen können.

Die Autoren schließen, dass, obwohl die exakte Zertifizierung eine fundamentale Herausforderung darstellt, die Barriere nicht nur eine Worst-Case-Anomalie ist, sondern eine strukturelle Konsequenz minimaler Überparametrisierung in Klassen, die für moderne Schlussfolgerungsaufgaben relevant sind. Sie schlagen vor, dass zukünftige Arbeiten aktive Zertifizierungsprotokolle untersuchen sollten, um diese passiven Barrieren möglicherweise zu überwinden.