AI RESEARCH
Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers
arXiv CS.LG
•
ArXi:2603.23823v1 Announce Type: new 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.