Ein ChatGPT-Klon auf Basis von GPT-2, implementiert in 3000 Byte C (2023)

• Mit rund 3000 Byte C-Code wird ein GPT-2-Inferenzprogramm aufgebaut, das vom Laden der Gewichte über die Tokenisierung und die Ausführung des Transformers bis zur Umwandlung der Ausgabe alles in einem durchgehenden Ablauf verarbeitet
• Trotz der kleinen Codegröße erzeugt es mit KV-Caching, schneller Matrixmultiplikation und optionaler OMP-Parallelisierung Antworten von GPT-2 Small auf modernen Maschinen in wenigen Sekunden
• Die Ausgabequalität liegt auf einem Niveau, das als „objektiv ziemlich schlecht“ beschrieben wird, und es bleiben praktische Einschränkungen wie die UTF-8-Verarbeitung und der Speicherbedarf beim Ausführen großer Modelle
• Die Implementierung ist in Matrixoperationen, neuronale Schichten, den Transformer, Byte Pair Encoding, I/O sowie das Laden von Gewichten und BPE aufgeteilt und zeigt damit die Gesamtstruktur eines kleinen Inferenzprogramms
• GPT-2 ist zwar ein deutlich schwächeres Open-Source-Modell von 2019 als GPT-4, aber die zentralen Bausteine moderner Sprachmodelle lassen sich dennoch in kleinem C-Code ausdrücken

---

Ein GPT-2-Laufzeitprogramm in 3000 Byte C

• Dieses Programm ist eine abhängigkeitsfreie GPT-2-Implementierung, die Gewichtsmatrizen und BPE-Dateien aus den ursprünglichen TensorFlow-Dateien einliest
• Die Eingabe wird mit einem einfachen Byte Pair Encoding (BPE)-Encoder tokenisiert, und die Ausgabe wird mit einem BPE-Decoder wieder in Text umgewandelt
• Der interne Aufbau reicht von einem grundlegenden linearen Algebra-Paket über Matrixoperationen und die Transformer-Architektur bis zum Inferenzcode
• Der Code ist auf GitHub veröffentlicht
• GPT-2 Small erzeugt auf modernen Maschinen in wenigen Sekunden eine Antwort
  • KV-Caching ist implementiert
  • Es wird eine effiziente Matrixmultiplikation verwendet
  • OMP-Parallelisierung kann optional aktiviert werden

Laufzeitbedingungen und Grenzen

• Mit dieser Implementierung lässt sich zwar ein dialogorientiertes Programm wie ChatGPT bauen, aber die Ausgabequalität ist nicht gut
• Bei der Verarbeitung von UTF-8-Zeichen gibt es einige Besonderheiten
• Wenn ein XL-Modell mit langer Kontextlänge ausgeführt wird, können etwa 100 GB RAM benötigt werden
• Mit ASCII-Eingaben und GPT-2 Small läuft es fast überall

GPT-2 und die Funktionsweise von Transformern

• ChatGPT ist eine Anwendung, die mit Menschen über ein Sprachmodell kommunizieren kann, und GPT-4 wird als aktuelles Modell beschrieben, das ChatGPT antreibt
• Dieses C-Programm bildet mit dem Modell GPT-2 von 2019 ein ChatGPT-ähnliches Verhalten nach
• GPT-2 ist ein Machine-Learning-Modell aus der Transformer-Familie
• Ein Transformer nimmt eine Wortsequenz fester Größe als Eingabe und sagt das nächste Wort voraus
• Wird derselbe Ablauf wiederholt, kann eine Sequenz beliebiger Länge erzeugt werden

Matrixoperationen und makrobasierte Komprimierung

• Da neuronale Netze aus Matrixoperationen bestehen, beginnt die Implementierung mit einer minimalen Matrix-Struktur
  • float* dat
  • int rows, cols
• Die benötigten Operationen lassen sich grob in zwei Typen einteilen
  • Matrix-Konstanten-Operationen
  • Matrix-Matrix-Operationen
• Mit C-Makros werden wiederkehrende Schleifenstrukturen reduziert, indem nur bestimmte Operatoren ausgetauscht werden, um mehrere Funktionen zu erzeugen
• Das #define in C ist fast reine Textersetzung, sodass zur Verringerung der Codegröße nicht nur gewöhnliche Operatoren, sondern sogar Ausdrücke mit Semikolons als Makroargumente verwendet werden können

Schnelle Matrixmultiplikation

• Die grundlegende Matrixmultiplikation startet mit einer einfachen O(n³)-Implementierung mit drei verschachtelten Schleifen
• Unter Berücksichtigung von Cache- und Speicherzugriffseigenschaften werden die Schleifen so umgestellt, dass derselbe Speicher wiederholt gelesen und beschrieben wird
• Die schnelle Implementierung erhöht j und k jeweils um 4 und verwendet intern die Schleifen k2 und j2
• Für den Inferenzschritt kommt zusätzlich eine Methode hinzu, bei der nur ein Teil der Matrix A mit B multipliziert wird, um bereits berechnete Ergebnisse wiederzuverwenden

Implementierung neuronaler Schichten

• Um den Transformer zu bauen, werden einige neuronale Schichten direkt implementiert
• Die GELU-Aktivierungsfunktion ist per Makro implementiert
• Für causal attention gibt es eine Funktion, die den unteren Dreiecksteil einer Matrix verarbeitet
  • Damit wird die Attention-Matrix so eingeschränkt, dass nur die Vergangenheit und keine zukünftigen Tokens betrachtet werden
• LayerNorm normalisiert Mittelwert und Varianz jeder Schicht
• Die Linear-Funktion addiert nach der Matrixmultiplikation den Bias per Tiling

Der Transformer-Kern

• Die Transformer-Implementierung wiederholt pro Schicht folgenden Ablauf
  • Über LayerNorm und Linear werden query, key, value in einem Schritt berechnet
  • qkv wird nach Heads aufgeteilt
  • Das Produkt aus query und key wird berechnet und causal attention angewendet
  • Das softmax-Ergebnis wird mit der value-Matrix multipliziert
  • Die Ergebnisse werden zusammengeführt und eine residual connection angewendet
  • Nach GELU und Linear folgt erneut eine residual connection
• Am Ende werden nach der abschließenden LayerNorm die Ausgaben an der Position des letzten Tokens mit den Embedding-Gewichten multipliziert, um die Kandidaten für das nächste Token zu berechnen

KV-Caching-Verfahren

• Bei der Transformer-Inferenz muss nach der Erzeugung eines Tokens für das nächste Token nicht die gesamte Funktion erneut berechnet werden
• Wenn der Großteil der Ergebnisse bis zum N-ten Token wiederverwendet wird, ist für die Erzeugung des N+1-ten Tokens nur noch zusätzliche Teilberechnung nötig
• Die Implementierung führt alle Allokationen nacheinander innerhalb desselben Speicherblocks aus
• Jede Matrixmultiplikation verwendet immer denselben Speicher, sodass der Speicher in der nächsten Iteration nicht auf 0 zurückgesetzt werden muss und frühere Ergebnisse erhalten bleiben
• In jeder neuen Iteration wird nur die Zeile N+1 berechnet

Implementierung von Byte Pair Encoding

• Sprachmodelle benötigen Eingaben fester Größe, daher ist es schwierig, unendlich viele Wörter unverändert auf Wortebene zu verarbeiten
• Zeichenbasierte Modelle müssten die Bedeutung jedes Wortes von Grund auf lernen und würden die effektive Kontextgröße um die durchschnittliche Wortlänge verringern
• Modelle wie GPT-2 verwenden BPE, bei dem Tokens aus Wortfragmenten gebildet werden
  • Häufige Wörter können ein einzelnes Token sein
  • Seltene Wörter werden in kleinere Teile zerlegt
  • Als Beispiel kann nicholas in nich, o, las aufgeteilt werden
• Der übliche BPE-Algorithmus führt wiederholt Merges benachbarter Token-Paare aus
• Diese C-Implementierung verwendet zur Verringerung der Codegröße statt eines linearen Algorithmus ein rekursives Verfahren, das potenziell exponentielle Laufzeit haben kann
  • Es wird nach einem Vokabulareintrag gesucht, der mit dem Präfix des aktuellen Wortes übereinstimmt
  • Der verbleibende String wird rekursiv tokenisiert
  • Die beste Tokenisierung wird anhand von Länge und Vokabularindex ausgewählt

Laden der Gewichte

• Die Gewichte des neuronalen Netzes müssen von der Festplatte gelesen werden; das Dateiformat ist eine flache binäre Serialisierung von 32-Bit-Floats
• Die GPT-2-Modellgrößen verwenden dieselbe Architektur, und auch die Gewichte sind in derselben Reihenfolge gespeichert, daher müssen nur Matrizen der richtigen Form der Reihe nach eingelesen werden
• Die Reihenfolge der gespeicherten Schichten unterscheidet sich von der erwarteten
  • Nach Schicht 0 und 1 folgt 10
  • Der Grund ist die Sortierung in lexicographic order
  • Bei der Zeichenkettensortierung steht 10 vor 2
• Die Implementierung verwendet Permutationscode, um diese Reihenfolge in die tatsächliche Schichtreihenfolge umzuwandeln

Laden des BPE-Vokabulars

• Um BPE auszuführen, muss zunächst die Vokabulardatei von der Festplatte eingelesen werden
• Die Originaldatei ist für das Einlesen in Python formatiert und nicht dafür ausgelegt, sich leicht mit kleinem C-Code parsen zu lassen
• Die Datei enthält keine Wortliste, sondern eine Liste von BPE-Merges
  • So wird zum Beispiel nicht das Token Hello direkt gespeichert, sondern dass H und ello zusammengeführt werden sollen
• Die Datei verwendet eine Kodierung, die UTF-8 ähnelt, aber nicht exakt UTF-8 ist
  • Druckbare ASCII-Zeichen werden unverändert gespeichert
  • Nicht druckbare Zeichen im Bereich 0 bis 31 werden als 188 + Zeichenwert kodiert
  • Ein Leerzeichen wird zum Beispiel als das Token Ġ kodiert
• Da Ġ auf der Festplatte in UTF-8 als 0xc4 0xa0 vorliegt, ist eine separate Verarbeitung nötig, um es wieder in ein Leerzeichen zurückzuverwandeln

Was der kleine Code zeigt

• Mehrere Jahrzehnte Machine-Learning-Entwicklung lassen sich in einigen tausend Byte Code verdichten
• Abgesehen von den eigentlichen Modellgewichten fehlt fast nichts von dem, was zum Ausführen moderner neuronaler Netze nötig ist
• Diese Implementierung wurde vor allem zum Spaß erstellt, zeigt aber anschaulich, dass neuronale Netze in der Praxis aus einfachen Bausteinen ausgeführt werden können

[GN⁺]

Meinungen auf Hacker News

• Ich habe den Code nicht selbst ausgeführt, aber beeindruckend ist, wie klein er ist.
  Wenn man bedenkt, dass die frühen ELIZA-Programme größer waren, heißt das: In den letzten vier Jahren ist es möglich geworden, so etwas byteweise hineinzupressen.
  Falls jemand weiß, wo die Magie steckt, würde ich mich über eine Erklärung freuen. Ich frage mich, ob es die GELU-Funktion ist oder das Modell, das per Bash-Skript heruntergeladen wird.

  • Der Großteil der Magie steckt in der 475-MB-Modelldatei, die per Bash-Skript heruntergeladen wird.
  • Ich habe es ausprobiert und fand es nicht besonders beeindruckend.
    Auf Who are you? antwortet es mit I am Alice., und wenn man nach Computern oder Funktionen fragt, wiederholt es I am a computer model trained by OpenAI. How can I help you?.
    Wenn man um eine Erklärung von Addition bittet, liefert es eine Erklärung von Multiplikation, und 2+2 oder Sum 2+2 spricht es im Grunde nur nach.

• Ich erinnere mich noch daran, wie ich mit GPT-2 herumgespielt habe, als es erstmals herauskam.
  Ein Freund und ich exportierten unsere Chat-Logs, finetunten GPT-2 darauf und ließen es Gespräche zwischen uns beiden imitieren; das war unglaublich lustig und manchmal unheimlich treffend.
  Ich frage mich, wodurch der Sprung von GPT-2 zu GPT-3 zustande kam. War es ein größeres Modell, mehr Daten oder beides?
  Ich weiß, dass RLHF einen großen Unterschied gemacht hat, aber auch das Basismodell von GPT-3 war schon ziemlich nützlich für reine Textvervollständigung, wenn man ihm genug Beispiele gab.

• Ich weiß nicht genau, aber es gibt einige meiner Lieblingsmärchen, die GPT-2 geschrieben hat.
  https://deepdreams.stavros.io/episodes/the-princess-the-fair...

  • Wirklich gut, tatsächlich unterhaltsam und auch schön, um dabei einzuschlafen.
    Ich frage mich, ob das mit dem GPT-2 von dieser Seite erstellt wurde.
  • Beeindruckend und seltsam, dabei aber zu etwa 90 % konsistent, was eine ganz eigene, bizarre Atmosphäre erzeugt.

• Die Stelle „das meiste davon ist nur zum Spaß, aber es ist ein gutes Beispiel dafür, wie einfach neuronale Netze tatsächlich sind“ ist amüsant.
  Psst, sagen wir es niemandem. Künstliche Intelligenz ist schwarze Magie, mit der man Geld verdient.

• Ist GPT-2 instruction-tuned, sodass man es tatsächlich für Chats verwenden kann?
  Falls nicht, finde ich es ziemlich weit hergeholt, das einen ChatGPT-Klon zu nennen.

  • Im Artikel steht bereits sinngemäß: Wenn einem die Ausgabequalität egal ist, kann man etwas ChatGPT-Ähnliches bauen; objektiv ist die Ausgabe ziemlich furchtbar, aber es läuft.
    Es ist praktisch unbrauchbar und hat außer der Anlehnung an den Namen kaum etwas damit zu tun. Trotzdem ist es ein Programm, das kompiliert und ausgeführt werden kann.
    Wenn man die Reaktionen sieht, die die Leistung eines Projekts loben, dessen Autor selbst einräumt, dass es nicht richtig funktioniert, scheint es letztlich vor allem darum zu gehen, mit Buzzwords Aufmerksamkeit zu erzeugen.

• Der Satz „Seht ihr, Sprachen mit richtigen Makros. Lisp ist nicht immer besser als C!“ ist diesmal akzeptabel. Der Witz geht nach oben.
  Falls ihr den Code-Link nicht gesehen habt: Er ist im Text versteckt: https://github.com/carlini/c-chat-gpt-2

• Ich habe schon bessere klassische KI-Chatbots gesehen.
  https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas...
  Splotch lässt sich mit kleinen Anpassungen auch auf modernen Unix-artigen Systemen gut kompilieren.

• Ich frage mich, ob jemand es lokal ausgeführt und sich angesehen hat, welche Ausgaben dieses GPT-2 erzeugt.

  • Es fühlt sich so an, als würde es fast immer dieselbe Ausgabe wiederholen.
    Trotzdem ist es ziemlich interessant, und ich würde gern selbst hineinschauen und daran herumjustieren. Ich wollte schon seit einer Weile lokal mit GPT-2 experimentieren.
  • Beim Lesen wirkt es so, als müssten das normal geladene GPT-2-Modell und das von diesem Programm geladene Modell bei gleicher Temperatur und gleichem Seed exakt dieselbe Ausgabe erzeugen.
    Temperatur und Seed konnte ich im Code nicht direkt überprüfen; ich war hauptsächlich dabei herauszufinden, warum er obfuskiert wurde.
    Selbst deobfuskiert dürfte der Code nicht extrem lang werden, und wenn er ungefähr 10.000 Zeichen hat, wäre schon allein die Betrachtung auf dem Bildschirm ausreichend beeindruckend.

• Heutzutage kann man mit gptscript sehr schnell sein eigenes ChatGPT implementieren.
  https://github.com/gptscript-ai/gptscript

• GELU wirkt wirklich wie Magie:
  UNARY(GELU, b / 2 * (1 + tanh(.7978845 * (b + .044715 * b * b * b))))

  • Das ist nur eine praktische Annäherung an die tatsächliche mathematische Definition von GELU.
    Die Definition lautet GELU(x) := x * Φ(x), wobei Φ(x) die kumulative Verteilungsfunktion der Gauß-Verteilung ist.
  • Die Form erinnert an die schnelle inverse Quadratwurzel.