[2603.23823] Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers

Computer Science > Machine Learning arXiv:2603.23823 (cs) [Submitted on 25 Mar 2026] Title:Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers Authors:Naiming Liu, Richard Baraniuk, Shashank Sonkar View a PDF of the paper titled Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers, by Naiming Liu and 1 other authors View PDF HTML (experimental) Abstract:Knowledge tracing models mastery over interconnected concepts, often organized by prerequisites. We analyze hierarchical prerequisite propagation through a circuit-complexity lens to clarify what is provable about transformer-style computation on deep concept hierarchies. Using recent results that log-precision transformers lie in logspace-uniform $\mathsf{TC}^0$, we formalize prerequisite-tree tasks including recursive-majority mastery propagation. Unconditionally, recursive-majority propagation lies in $\mathsf{NC}^1$ via $O(\log n)$-depth bounded-fanin circuits, while separating it from uniform $\mathsf{TC}^0$ would require major progress on open lower bounds. Under a monotonicity restriction, we obtain an unconditional barrier: alternating ALL/ANY prerequisite trees yield a strict depth hierarchy for \emph{monotone} threshold circuits. Empirically, transformer encoders trained on recursive-majority trees converge to permutation-invariant shortcuts; explicit structure alone does not prevent this, but auxiliary supervision on ...