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

Naiming Liu, Richard Baraniuk, Shashank Sonkar · 2026

Read Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers by Naiming Liu, Richard Baraniuk, Shashank Sonkar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-23823.txt.

Introduction

Liu and co-authors analyze knowledge tracing on concept trees through circuit complexity. Knowledge tracing tracks mastery across linked concepts with prerequisites. They model tasks such as recursive-majority propagation up a prerequisite tree. Such tasks sit in NC1, while proving them beyond TC0 would need major open results. Under a monotone restriction, they prove a strict depth hierarchy. In tests, transformers learn shortcuts unless trained on intermediate subtrees. Extra supervision then yields near-perfect scores at depths three and four.

Catalog record

CREATORNaiming Liu, Richard Baraniuk, Shashank Sonkar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34216
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.23823

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers Naiming Liu, Richard Baraniuk, Shashank Sonkar 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 𝖳𝖢 0 \mathsf{TC}^{0} , we formalize prerequisite-tree tasks including recursive-majority mastery propagation. Unconditionally, recursive-majority propagation lies in 𝖭𝖢 1 \mathsf{NC}^{1} via O ⁡ ( log ⁡ n ) O(\log n) -depth bounded-fanin circuits, while separating it from uniform 𝖳𝖢 0 \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 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. 1 Introduction Knowledge tracing, modeling how learners master interconnected concepts over time, is fundamental to student modeling, intelligent tutoring systems, and adaptive learning [ 6 , 26 , 14 ] . A central challenge is capturing how mastery of prerequisite concepts propagates through a concept hierarchy to enable (or block) mastery of more advanced concepts. While a large body of work has explored neural architectures for knowledge tracing, the computational capabilities and limitations of these models remain poorly characterized [ 22 , 34 , 25 , 7 , 31 ] . This paper takes a circuit-complexity perspective on hierarchical prerequisite reasoning. Recent results show that log-precision transformers , transformers whose activations use O(\log n) bits on inputs of length n , can be simulated by logspace-uniform constant-depth threshold circuits, i.e., they lie in logspace-uniform \mathsf{TC}^{0} [ 18 , 17 ] . This connection suggests a natural route to transformer limitations: exhibit knowledge-tracing functions that lie beyond (uniform) \mathsf{TC}^{0} . However, proving such lower bounds for general \mathsf{TC}^{0} is notoriously difficult and is intertwined with major open questions in circuit complexity, for example separating \mathsf{TC}^{0} from \mathsf{NC}^{1} [ 30 ] . We formalize prerequisite propagation on deep concept hierarchies using balanced prerequisite trees and study what can be proved unconditionally versus what remains open for standard (non-monotone) transformers. As a baseline, we define a natural hierarchical mastery rule in which each internal concept is mastered if a majority of its prerequisites are mastered; computing the root mastery then corresponds to evaluating a depth- \Theta(\log n) majority formula, placing the task in \mathsf{NC}^{1} [ 30 ] . Showing that this function is not in (uniform) \mathsf{TC}^{0} would yield an immediate limitation for log-precision transformers, but would also constitute a significant circuit lower bound beyond current techniques. To provide unconditional evidence that layered prerequisite structure can resist shallow parallelization, we also analyze an alternating prerequisite model (ALL/ANY requirements), which corresponds to evaluation of alternating \wedge/\vee trees. From an educational modeling perspective, prerequisite aggregation is naturally monotone in prerequisite mastery: holding the curriculum fixed, mastering additional prerequisites should not reduce a learner’s readiness for an advanced concept. This monotonicity is a common desideratum in mastery models because it aligns with the semantics of prerequisite structure and improves interpretability. We therefore analyze an alternating ALL/ANY prerequisite rule under monotone threshold computation as a principled restricted setting in which unconditional depth lower bounds are known. Here, classical results establish a strict depth hierarchy for monotone threshold circuits: increasing prerequisite depth provably increases the power required, and reducing depth forces superpolynomial (indeed exponential) size [ 33 , 13 ] . While these monotone lower bounds do not directly apply to standard transformers (which are not monotone), they delineate a principled barrier and clarify which additional restrictions would be needed to obtain unconditional transformer impossibility results. Our contributions provide a landscape view of prerequisite-tree knowledge tracing: 1. Formalization and complexity accounting. We formalize prerequisite propagation on balanced concept trees under natural mastery rules, including recursive majority, and connect these tasks to standard circuit-evaluation problems. 2. What is provable today. Unconditionally, for fixed arity k , recursive-majority prerequisite propagation is computable by logarithmic-depth bounded-fanin circuits, placing it in \mathsf{NC}^{1} ; in contrast, proving separation from (uniform) \mathsf{TC}^{0} would require major progress on circuit lower bounds. 3. Barriers and empirical diagnostics. For an alternating ALL/ANY prerequisite rule, classical results yield a strict depth hierarchy for monotone threshold circuits, showing that layered prerequisite structure can resist shallow parallelization under monotonicity constraints. Empirically, transformer encoders trained on recursive-majority trees learn permutation-invariant shortcuts under root-only supervision; explicit structure alone does not prevent this, but auxiliary supervision on intermediate subtrees elicits structure-dependent computation at moderate depths. Taken together, these results clarify both the promise and the limits of current theory. Hierarchical prerequisite reasoning naturally induces logarithmic-depth computation, and unconditional lower bounds for general \mathsf{TC}^{0} remain out of reach. Our empirical results complement this view by showing that, even with explicit structure, models can learn shortcuts unless training rewards intermediate prerequisite propagation. 2 Related Work Our work connects three threads: (i) circuit-complexity characterizations of transformer-like architectures, (ii) modeling choices in knowledge tracing (especially prerequisite structure), and (iii) neural mechanisms for recursive / hierarchical computation. 2.1 Theoretical Analysis of Transformer Computation A growing line of work characterizes transformers via circuit complexity. Merrill and Sabharwal [ 18 ] show that log-precision transformers—those whose activations use O(\log n) bits on length- n inputs—can be simulated by logspace-uniform constant-depth threshold circuits, placing them within logspace-uniform \mathsf{TC}^{0} . Related analyses of restricted or saturated transformer variants connect attention-based computation to constant-depth threshold circuit families [ 17 ] . These results motivate a principled route to expressivity limitations: if a target function can be shown to lie beyond (uniform) \mathsf{TC}^{0} , then it is unreachable by log-precision transformers in this single-pass setting. Other work studies how specific architectural choices (e.g., attention constraints, normalization) affect expressivity on formal-language tasks [ 11 , 4 ] . Strobl et al. [ 27 ] provide a useful synthesis, which harmonizes expressivity results across transformer variants and situates them in the standard circuit hierarchy \mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}\subseteq\mathsf{L} . Importantly, while many natural recursive computations (e.g., Boolean formula evaluation) lie in \mathsf{NC}^{1} , proving that such problems are not computable by general \mathsf{TC}^{0} circuits would imply major open lower bounds (e.g., separating \mathsf{TC}^{0} from \mathsf{NC}^{1} ). Our paper is explicitly motivated by this gap: we identify educationally meaningful hierarchical reasoning tasks that naturally land in \mathsf{NC}^{1} , and we clarify what is currently provable versus what remains open for general \mathsf{TC}^{0} -style transformer computation. 2.2 Knowledge Tracing Methods and Prerequisite Structure Knowledge tracing (KT) began with Bayesian Knowledge Tracing (BKT) [ 6 ] , which models binary mastery via hidden states. Deep learning approaches shifted KT toward representation learning from interaction sequences. Deep Knowledge Tracing (DKT) [ 22 ] applies RNNs to student-event sequences, while DKVMN [ 34 ] introduces key–value memory to separate concept representations from student mastery states. Transformers have since become prominent in KT. SAKT [ 20 ] uses self-attention to retrieve relevant past interactions; AKT [ 7 ] incorporates monotonicity and temporal effects. Subsequent work explores

Read the complete text