# Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers

arXiv: https://arxiv.org/abs/2603.23823 · HTML: https://mlsanity.com/paper/2603.23823/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 25 Mar 2026.

## Builds on (most cited first, 19 of 19)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Deep Knowledge Tracing](https://mlsanity.com/paper/1506.05908/) (2015)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Context-Aware Attentive Knowledge Tracing](https://mlsanity.com/paper/2007.12324/) (2020)
- [A Self-Attentive model for Knowledge Tracing](https://mlsanity.com/paper/1907.06837/) (2019)
- [Dynamic Key-Value Memory Networks for Knowledge Tracing](https://mlsanity.com/paper/1611.08108/) (2016)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Towards an Appropriate Query, Key, and Value Computation for Knowledge Tracing](https://mlsanity.com/paper/2002.07033/) (2020)
- [RKT : Relation-Aware Self-Attention for Knowledge Tracing](https://mlsanity.com/paper/2008.12736/) (2020)
- [GIKT: A Graph-based Interaction Model for Knowledge Tracing](https://mlsanity.com/paper/2009.05991/) (2020)
- [qDKT: Question-centric Deep Knowledge Tracing](https://mlsanity.com/paper/2005.12442/) (2020)
- [FoundationalASSIST: An Educational Dataset for Foundational Knowledge Tracing and Pedagogical Grounding of LLMs](https://mlsanity.com/paper/2602.00070/) (2026)

## Abstract (arXiv)

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 mathsfTC0, we formalize prerequisite-tree tasks including recursive-majority mastery propagation. Unconditionally, recursive-majority propagation lies in mathsfNC1 via O(log n)-depth bounded-fanin circuits, while separating it from uniform mathsfTC0 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 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.