研究知识追踪中深层概念层级的计算复杂性，揭示Transformer的局限与改进方向。
Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers
- 用电路复杂度分析概念层级传播，发现递归多数传播属于NC¹类
- 实验证明模型易学捷径，中间层监督可提升至3-4层深度的近完美准确率
- 适用于需要结构感知的深度知识追踪系统设计者
知识追踪模型用于刻画对相互关联概念的掌握程度，这些概念常具有前置依赖关系。本文从电路复杂度视角分析变压器式计算在深层概念层级上的表现。利用近期结果：对数精度的变压器属于对数空间均匀的TC⁰类，我们形式化了包括递归多数掌握传播在内的前置树任务。无条件地，递归多数传播可由O(log n)深度的有界扇入电路实现，属于NC¹；而将其与统一的TC⁰分离需重大下界突破。在单调性限制下，我们获得一个无条件障碍：交替的全部/任意前置树在单调阈值电路中产生严格深度层级。实验上，训练于递归多数树的变压器编码器会收敛到排列不变的捷径；仅显式结构不足以阻止此现象，但对中间子树施加辅助监督可激发结构依赖计算，并在深度3–4时达到接近完美的准确率。这些发现推动了面向深层层级的结构感知目标与迭代机制的设计。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。