Neural networks can provably represent many algorithms that training never discovers. Parity of a long bit string, multi-step visual reasoning, and compositional command parsing all have known exact weight constructions. Yet end-to-end gradient descent on input–output pairs fails on them, because the gradient signal for the correct solution shrinks to almost nothing as the number of chained steps grows. The one reliable fix is to supervise every intermediate step of the computation, which the literature calls trace supervision. Its cost grows with the length of the computation and the number of examples. This note asks whether that cost can be cut sharply by letting the model choose which intermediate steps to have labeled. It would request a label only for the internal states it is unsure about, and it would rely on end-to-end training for the rest.
The core claim is that learnability on these tasks depends on where intermediate supervision is placed, not on how dense it is. A model's own uncertainty about its intermediate states is a cheap, adaptive guide to placement. Uncertainty here means disagreement among a small ensemble of probe heads that each predict the hidden algorithmic state. If the claim is right, a small, shrinking budget of trace labels, concentrated on the steps the network has not yet internalized, should match full trace supervision on length generalization. If it is wrong, the budget-matched controls described below will show it, and they will also show whether the simpler explanation, "evenly spaced labels are enough," accounts for any gains.
Where the two directions meet
The motivating evidence comes from work on the gap between what networks can represent and what they can learn. Failures of Gradient-Based Deep Learning shows that on a multi-step visual parity task, end-to-end training collapses at $k \ge 3$ chained sub-tasks because gradient signal-to-noise ratio decays exponentially, while supervising the decomposition solves any $k$. A Spectral Perspective On Generalization in Transformers explains this in Fourier terms. A single forward pass over length-$T$ parity carries an $O(2^T)$ error bound, while step-by-step supervision breaks the problem into degree-2 pieces with an $O(T)$ bound. ALTA: Compiler-Based Analysis of Transformers compiles symbolic programs into Transformer weights. It shows that standard training drifts toward brittle shortcuts, such as a "sum then modulo" heuristic for parity. It also shows that full execution-trace supervision gives 100% accuracy on longer parity strings and on SCAN compositional splits. These three papers establish that intermediate labels close the gap. None of them asks how few labels are needed, or which ones.
The method side comes from uncertainty-based active learning, and the closest bridging work constrains the design more than it anticipates it. Active Data Curation Effectively Distills Large-Scale Multimodal Models selects training examples where a teacher is confident but the student is not. Learnability Matters: Active Learning for Video Captioning filters out examples whose high uncertainty reflects contradictory annotations before querying the rest. Both choose which inputs to train on. We choose which positions inside a computation to supervise, which is a different action space. Probing the Decision Boundaries of In-context Learning in Large Language Models shows that uncertainty-driven exemplar choice smooths fragmented decision boundaries, but only for frozen models doing in-context inference, with no gradient updates.
One negative result shapes the design directly. Formal Models of Active Learning from Contrastive Examples proves that active contrastive queries give no advantage for learning parity under Hamming distance. Our reading is that choosing inputs cannot help on parity, because every input is equally uninformative about the hidden subset. Querying an intermediate state is a different oracle: it reveals part of the computation itself. The proposal deliberately avoids input selection for this reason.
Research Program
The setup attaches lightweight probe heads to the network that predict the symbolic state at each step of the target algorithm. These states are the running parity bit, the slope of each line image, or the stack and buffer configuration of a shift-reduce parser for SCAN. We train $M$ such heads with different seeds as an ensemble.
For each training example and each step $t$, the selection score is the ensemble's epistemic disagreement. We measure it as mutual information between the head identity and the predicted state:
$$ u_t(x) = H\Big[\tfrac{1}{M}\textstyle\sum_{m} p_m(s_t \mid x)\Big] - \tfrac{1}{M}\textstyle\sum_{m} H\big[p_m(s_t \mid x)\big]. $$
Here $p_m(s_t \mid x)$ is head $m$'s predicted distribution over the intermediate state $s_t$ for input $x$, and $H$ is entropy. Disagreement rather than raw entropy is used so that steps the model is uniformly unsure about at initialization do not all look equally urgent once some heads have learned.
At each round, a budget of $B$ step labels is spent on the highest-scoring (example, step) pairs. The labels come from a program oracle that executes the reference algorithm. The labeled steps receive an auxiliary cross-entropy loss, and all examples keep the end-to-end loss. Training starts from a small random seed set of step labels to avoid a cold start. Probe heads read from early layers where possible, following the cheap early-layer entropy approach of Understanding the Training Speedup from Sampling with Approximate Losses, so that scoring stays cheap relative to training.
The analysis component measures gradient signal-to-noise ratio for each layer and each step, following the definition in Failures of Gradient-Based Deep Learning. Tracking it over training under each placement policy tests the proposed mechanism directly. A label at step $t$ should raise the signal-to-noise ratio for the stretch of computation between it and the nearest other supervised step. The prediction from the Fourier view is that difficulty is governed by the longest unsupervised stretch, since the Fourier degree a gradient must cross grows with stretch length. That makes the maximum gap between labels, not the label count, the quantity active placement should shrink.
A second prediction concerns how the policy behaves over time. Once a sub-step is internalized, its disagreement drops and labels move elsewhere. The label rate per example should therefore fall over training. That fall is the source of any saving over full traces, and we will report it as a curve.
Baselines
The naive reference is end-to-end training on input–output pairs with no intermediate labels, at matched model size, optimizer, and step count. On multi-step visual parity this is expected to fail beyond $k=3$, as Failures of Gradient-Based Deep Learning reports. On parity and SCAN it is expected to fail on longer or compositional test splits, as ALTA reports. Every method must clear this floor.
The strongest existing method is full trace supervision as in ALTA. ALTA reports 100% accuracy on parity sequences longer than training strings and 100% on SCAN compositional splits with its compiled shift-reduce parser. The decomposition baseline of Failures of Gradient-Based Deep Learning solves visual parity for any $k$. No reported result was found on Lacuna for partial or budgeted trace supervision on any of these tasks. We will run full supervision with the same architecture, probe heads, data, and step count, and treat it as the accuracy ceiling. Beating it means matching its out-of-distribution accuracy to within one point while using at most a fifth of its intermediate labels.
The ablation that isolates our key ingredient comes in two parts at equal label budget. Random placement chooses (example, step) pairs uniformly. Fixed-stride placement supervises every $m$-th step, with $m$ set so the budget matches. Fixed stride is the important control, because it already equalizes gaps between labels without using any uncertainty. All three placement policies get the same probe heads, the same seed set, and the same hyperparameter search budget, which consists of twenty configurations each, selected on in-distribution validation only. Uncertainty placement wins only if it reaches the target accuracy with fewer labels than fixed stride, averaged over at least five seeds.
Why not just…?
Why not just supervise every $m$-th step? This is the most serious threat. On uniform tasks like sequential parity, every step is equally hard, so a fixed stride may be nearly optimal, and we expect active placement to merely tie there. The claim is that adaptivity pays off when step difficulty varies. Examples are SCAN, where many parser transitions are trivial and a few (nested repetition, conjunction) are hard, and multi-step tasks that mix easy and hard sub-functions. We will build a heterogeneous variant of visual parity by giving some positions harder image sub-tasks than others. If active placement does not beat stride there either, we will report that spacing, not uncertainty, is what matters.
Why not just use a length curriculum, training on short sequences first? A curriculum needs no intermediate labels, which makes it attractive. But Overcoming a Theoretical Limitation of Self-Attention shows that training on long strings remains spiky, with influence per token decaying as $O(1/n)$. ALTA also shows that short-sequence training converges to shortcuts that break at longer lengths. We will include a short-to-long curriculum with zero step labels as a baseline, and also combine it with each placement policy, to test whether the two are complementary.
Why not just fix the initialization or the activation function? Learning High-Degree Parities: The Crucial Role of the Initialization shows that discrete $\pm 1$ initialization makes dense parity learnable. The same paper shows this collapses under Gaussian perturbation of size $O(d^{-1})$. Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent needs polynomial activations matched to the sparsity of the parity. Neither fix carries over to Transformers parsing SCAN. Our method keeps standard initialization and activations, so it can be applied wherever traces exist.
Why not just scale the model? Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent reports a 300,000-parameter MLP that does not generalize until it has nearly memorized the truth table. We will still run a model four times wider without labels as a sanity check.
Proposed Experiments
We will use three task families. The first is multi-step visual parity from Failures of Gradient-Based Deep Learning with $k$ from 2 to 8, plus the heterogeneous variant described above. The second is sequential parity with training on short strings and testing on strings up to ten times longer, as in ALTA and Cholak and Chiang. The third is SCAN length and compositional splits with shift-reduce traces generated by the ALTA reference program. The primary metric is the number of step labels needed to reach 99% out-of-distribution accuracy. Secondary metrics are the per-layer gradient signal-to-noise ratio, the maximum unsupervised gap, and wall-clock overhead from scoring.
Three checks are decisive. First, on visual parity, labels-to-target should grow exponentially in $k$ for end-to-end training and linearly for full traces. For active placement it should grow linearly but with a small slope, and the label rate per example should fall during training. Second, on the heterogeneous tasks, active placement must beat fixed stride at equal budget. Otherwise the uncertainty component is unjustified. Third, the signal-to-noise traces must show that steps selected by disagreement are the ones where gradient signal had collapsed. If disagreement and low signal-to-noise ratio do not line up, the method would be working for reasons other than the one proposed.
As a robustness check, we will corrupt 20% of oracle step labels to simulate imperfect annotators. Under this condition we will compare maximum-disagreement selection with median-uncertainty selection, the rule Privacy-preserving and Uncertainty-aware Federated Trajectory Prediction for Connected Autonomous Vehicles found avoids selecting unlearnable cases. This tests whether the same noise trap that affects input selection also affects selection of internal steps.
References
- Failures of Gradient-Based Deep Learning
- A Spectral Perspective On Generalization in Transformers
- ALTA: Compiler-Based Analysis of Transformers
- Active Data Curation Effectively Distills Large-Scale Multimodal Models
- Learnability Matters: Active Learning for Video Captioning
- Probing the Decision Boundaries of In-context Learning in Large Language Models Download PDF
- Formal Models of Active Learning from Contrastive Examples
- Understanding the Training Speedup from Sampling with Approximate Losses
- Overcoming a Theoretical Limitation of Self-Attention
- Learning High-Degree Parities: The Crucial Role of the Initialization
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent
- Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
- Privacy-Preserving and Uncertainty-Aware Federated Trajectory Prediction for Connected Autonomous Vehicles