Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers
This work addresses the problem of understanding transformer limitations in hierarchical knowledge tracing for AI education systems, providing theoretical insights and empirical guidance, though it is incremental in building on existing circuit complexity results.
The paper analyzed hierarchical knowledge tracing through circuit complexity, showing that recursive-majority propagation is in NC¹ and separating it from uniform TC⁰ would require major lower-bound progress, while under monotonicity, it yields a strict depth hierarchy for monotone threshold circuits. Empirically, transformer encoders converged to shortcuts but with auxiliary supervision achieved near-perfect accuracy at depths 3-4.
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 intermediate subtrees elicits structure-dependent computation and achieves near-perfect accuracy at depths 3--4. These findings motivate structure-aware objectives and iterative mechanisms for prerequisite-sensitive knowledge tracing on deep hierarchies.