계층적 지식 추적의 회로 복잡성 분석 및 로그 정밀 변환기에 대한 함의

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

지식 추적 모델은 종종 선행 관계에 의해 구성된 상호 연결된 개념에 대한 숙련도를 파악합니다. 본 연구에서는 변환기 기반 컴퓨팅이 깊은 개념 계층에서 수행될 때, 회로 복잡성 관점에서 계층적 선행 관계 전파에 대한 분석을 통해 증명 가능한 내용을 명확히 합니다. 최근 연구 결과에 따르면, 로그 정밀 변환기는 로그 공간 균일 $ ext{TC}^0$에 속합니다. 본 연구에서는 재귀적 다수 숙련도 전파를 포함한 선행 관계 트리 기반 작업을 형식화합니다. 조건부 없이, 재귀적 다수 전파는 $O( ext{log } n)$-깊이의 제한된 팬인 회로를 통해 $ ext{NC}^1$에 속하며, 이를 균일 $ ext{TC}^0$와 분리하려면 아직 해결되지 않은 하한에 대한 상당한 진전이 필요합니다. 단조성 제약 조건 하에서는, 교대 ALL/ANY 선행 관계 트리가 단조 임계 회로에 대한 엄격한 깊이 계층 구조를 형성한다는 무조건적인 장벽을 얻습니다. 실증적으로, 재귀적 다수 트리를 사용하여 학습된 변환기 인코더는 순열 불변 단축 경로로 수렴합니다. 명시적인 구조만으로는 이를 방지할 수 없지만, 중간 부분 트리에 대한 추가적인 감독 학습은 구조에 의존적인 계산을 유도하고 깊이 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.