Neue Erkenntnisse zur Komplexität von Hierarchischen Wissensverfolgung & Log-Precision Transformers

Eine aktuelle Studie auf arXiv beleuchtet die theoretische Basis von Wissensverfolgungsmodellen, die Lernfortschritte über miteinander verknüpfte Konzepte hinweg verfolgen. Dabei liegt der Fokus auf hierarchisch aufgebauten Prerequisite-Strukturen und deren Berechnung durch Transformer‑Architekturen mit logarithmischer Präzision.

Die Autoren analysieren die Propagation von Mastery‑Informationen entlang von Prerequisite‑Bäumen aus der Perspektive der Schaltkreis‑Komplexität. Sie nutzen neueste Resultate, die zeigen, dass Log‑Precision‑Transformers in der Klasse logspace‑uniform TC⁰ liegen, um Aufgaben wie die rekursive Majority‑Propagation formal zu beschreiben. Unbedingt gilt, dass diese Aufgabe in NC¹ liegt, weil sie mit O(log n)-Tiefe, begrenzter Fan‑In‑Schaltkreisen realisiert werden kann. Eine Trennung von NC¹ und TC⁰ würde jedoch bedeutende Fortschritte in offenen unteren Schranken erfordern.

Unter einer Monotonie‑Beschränkung erhalten die Forscher eine unbedingte Schranke: Alternierende ALL/ANY‑Prerquisite‑Bäume erzeugen eine strenge Tiefenhierarchie für monotone Schwellen‑Schaltkreise. Diese theoretische Grenze unterstreicht die Komplexität, die tief verschachtelte Wissenshierarchien mit sich bringen.

Experimentell zeigen die Ergebnisse, dass Transformer‑Encoder, die auf rekursiven Majority‑Bäumen trainiert werden, zu permutation‑invarianten Kurzschlüssen neigen. Die reine Struktur verhindert dies nicht, doch zusätzliche Supervision auf Zwischenschritten führt zu strukturabhängiger Berechnung und erzielt bei Tiefen von drei bis vier nahezu perfekte Genauigkeit. Diese Befunde legen nahe, dass strukturorientierte Ziele und iterative Mechanismen für wissenssensitives Tracking in tiefen Hierarchien weiterentwickelt werden sollten.