acceptodds
Under review as a conference paper at ICLR 2027

Beyond Labels: PAC Learning with Intermediate Supervision

Abstract

The traditional learning paradigm relies on input-label pairs but as concept classes become increasingly complex, learning becomes statistically and computationally expensive. Modern machine learning bypasses this problem using intermediate supervision like chain-of-thought and distillation to speed up learning. Although widely explored in practice, its theoretical understanding remains limited. We study the PAC learnability of deep models composed of intermediate gates with partial information about their outputs, revealed only during training. Our flexible concept class captures a wide range of architectures, including deep ReLU networks and transformers and uses gates in layers to map a dimensional feature to a label. While learning is computationally intractable even for one-hidden-layer networks, we show that mild intermediate supervision makes deep models efficiently learnable. We study different degrees of intermediate supervision ranging from exact intermediate traces to partial and noisy information. We provide tight characterizations of the computational complexity; the exact case is fully polynomial in , while the partial and noisy cases are polynomial for constant which we show that is unavoidable by proving a corresponding cryptographic hardness result. Finally, experiments demonstrate the benefits of intermediate supervision in cases where classical label-only approaches fail.

Primary area:
learning theory
Keywords:
PAC learning, neural networks, transformers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_ku5WOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies an important question of what intermediate information, about the inference process, can help in learning. This is a very well-posed timely question. One of the central challenges in such problems is to model correctly the type of intermediate information to be studied.

The model presented in this work is the intermediate calculations of a piecewise linear machine: intermediate calculation are divided into "activation" (s) and output (h). The paper first conclusion is that learning is possible in the face of both. In the second part they show that s are enough and finally they show that permuted s are also sufficient.

Since such models rarely capture reality faithfully, their main contribution often lies in the novelty of the ideas and techniques they introduce. So my review will focus on two issues. The first is the technical strength of the results which, overall, I think they are sound and and require some sophistication. The second issue is related the literature survey, which I find more imminent.

The first result seems technically trivial. This is not something bad, I think it is good to start with a technically simple setting to illustrate the scope. But overall, the first setting simply allow to learn each output-node individually, and the final output follows recursively. From my understanding the current paper doesn't improve on this approach.

The second result seems more technically involved as the outputs are not given. A naive approach could learn for each sign-configuration a classifier but that would be exponential in depth. The authors observe the linearity of each output layer and hence are able to achieve bounds that are polynomial in width.

The third result, when order of signals is not provided, I found least appealing: The result seems exponential in the number of nodes. With that, I don't see the advantage of their suggested solution that simply going brute-force over all permutation and perform pac learning using the second result. As far as I can see that would give almost the same dependence: it is K! instead of 2^{K}. There is some incremental improvement, but if this improvement is the point, then it should be put in better context.

As to related work. There seems to be several paper that touched the issue and I think those should have been discussed.

  1. Neural Path Features and Neural Path Kernel :Understanding the role of gates in deep learning: Their proposition suggests an embedding of each example in an ambient space given the signs. This result, I believe allows to learn a classifier at the same rate as suggested in this work. It is true that at inference, the signs are not given. So I think some discussion is warranted, but there is enough novelty here.

  2. Auto-Regressive Next-Token Predictors are Universal Learners: This paper studies a seemingly different problem of learning a kind of next bit prediction problem. But they specifically state that such relus with activations can be cast into their model, hence suggesting an algorithm to learn this problem (theorems 3.3 3.6 3.8 all seem relevant)

  3. Learning Complicated Concepts eliably and Usefully: This is indeed an old work, but section 2.2 deals with the question of learning when the pieces of a circuit are presented. The current paper speaks in a modern language of networks, but morally, these are not that different.

Critical strengths

The problem is timely and the model is natural.

Critical weaknesses

Related work is was not properly investigated.

Questions for authors

I have no questions.

2 comments

We thank the reviewer for the careful review. Below we address the reviewer’s comments and questions, and we would be happy to provide further clarification if needed.

Q1. Related work was not properly investigated ...

A1. A key contribution is a computational separation: complete activation signs can leave learning hard, whereas numerical activations make the same ReLU class efficiently learnable.

Theorem 4 establishes this by constructing networks whose entire sign trace is computable from the input independently of the unknown target, while the numerical states actually carry the hard computation. Cryptographic hardness therefore persists even when the signs are available at prediction time. In contrast, Corollary 1 gives polynomial-time learning from numerical activations revealed only during training, under the same distribution-free setting and output-disagreement loss.

Our positive results identify when learning remains possible despite the missing numerical states. Theorem 2 shows how to combine learners for the individual steps into a predictor for the full computation, reconstructing the intermediate trace instead of requiring it at test time. Corollaries 2–3 construct distribution-free learners from ReLU signs and attention traces, including reconstruction at prediction time. Theorem 3 quantifies error propagation for inexact traces, and Theorem 5 gives an efficient regime under explicit path-margin and norm conditions. Together, these results establish the capabilities but also the limitations of partial intermediate supervision.

These works are closely related, and we will cite and discuss them explicitly. Our results address what can be learned when signs or routes are observed but numerical states remain hidden. More specifically, the cited works do not establish the separation we just mentioned between learning from signs and learning from numerical activations.

Q2. The first result seems technically trivial ...

A2. The complete-trace result is intentionally the simplest setting. Corollary 1 gives a proper, distribution-free learner for ReLU networks with polynomial dependence on dimension, width, and depth, using numerical activations only during training. This provides the baseline against which the partial-trace results can be understood. We will connect it explicitly to earlier circuit-learning work, including Rivest & Sloan's Section 2.2.

Q3. Neural Path Features and Neural Path Kernel ... allows to learn a classifier at the same rate ...

A3. The path representation makes the output linear once the gates are known. Our learning problem also requires recovering those gates from the input, since the teacher's trace is unavailable at prediction time. Corollary 2 establishes this by learning each gate in features constructed from earlier signs and composing the learned predictors. We will credit the existing representation and make this additional learning guarantee explicit.

Q4. Auto-Regressive Next-Token Predictors are Universal Learners ...

A4. Malach's Theorems 3.3 and 3.6 show how learning individual steps can yield accurate predictions for the full computation. The difference is what the intermediate supervision reveals. In the Boolean-circuit construction of Theorem 3.8, each observed bit is the value passed to subsequent gates. Our ReLU signs are also bits, but they reveal only whether a neuron is active; subsequent layers use its numerical activation, which remains hidden. We show that you can actually use these partial observations to construct useful features that make the local prediction problems learnable, and we will clarify this connection in the related-work discussion.

Q5. I don't see the advantage of their suggested solution ... going brute-force over all permutation ...

A5. Enumerating candidate orders is a valid baseline. Appendix E instead uses subset features and validation to progressively learn a usable prediction order, without recovering the teacher's original ordering. Its guarantee is polynomial in d2Kd2^K, where KK is the number of gates, and therefore remains exponential. We will explain the comparison with enumeration explicitly and clarify the result's role: extending learnability to traces whose gate identities and layer assignments are unknown.

Thank you for the rebuttal and for addressing the points raised in my review. I have read your response and will take it into account when reassessing my score during the discussion period.

Reviewer_6bwqOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how training-time access to a teacher network’s intermediate computations affects computational PAC learnability. It introduces gated linear programs and considers complete numerical states, discrete activation or routing traces, and noisy numerical observations. Complete traces enable layerwise learning under learnability assumptions on the gates. Partial traces are handled through expanded features and local-to-global composition arguments. The paper also establishes cryptographic hardness results for discrete traces and gives a kernel-based learning guarantee under path-margin and norm assumptions. Empirical validation is limited to synthetic parity tasks using a shared, small ReLU computation.

Critical strengths

The distinction between numerical hidden states and discrete control-flow information is the clearest conceptual contribution. In particular, the hardness constructions illustrate that revealing every activation sign or attention route need not reveal the numerical content carried by the computation. This provides a useful qualification to the broad intuition that additional intermediate supervision necessarily makes learning computationally easy.

Critical weaknesses
  1. Limited demonstrated significance. The paper does not clearly establish its substantive advance over existing intermediate-supervision theory. The positive results rely on exact traces, learnable local components, or path-margin and norm assumptions whose relevance to meaningful deep networks is not demonstrated.

  2. Claims exceed the supporting evidence. The claimed “tight characterizations” are not supported by matching upper and lower bounds under the same settings and losses. Experiments are limited to a synthetic parity task and do not assess the attention, noisy-trace, or path-margin results. Large-scale benchmarks are not essential, but examples directly demonstrating why the key assumptions and distinctions matter are needed.

Questions for authors
  1. What precise learnability result goes beyond the closest existing theory of intermediate or CoT supervision?

  2. Which upper and lower bounds match under the same supervision model and loss, justifying the claimed “tight characterizations”?

  3. Can you identify a nontrivial deep-network family for which both 1/γ and B in Theorem 5 are polynomially bounded? Do the parity experiments satisfy these conditions?

  4. Are the length-generalization protocols in the main text and Appendix H separate experiments? Please clarify which protocol supports Figure 1.

1 comment

We thank the reviewer for taking the time to review our paper. Below we address each of the reviewer’s comments and questions.

W1. Limited demonstrated significance ... + Q1. What precise learnability result goes ...

A1. Our work provides a general framework for PAC learning with intermediate supervision in deep neural models. Learning even small ReLU networks from input–output pairs alone can be computationally hard (Daniely and Vardi, 2021; Chen et al., 2022). Starting from this limitation, we ask what else we can reveal, only during training, to make learning efficient. Modern machine learning already uses intermediate supervision, and our work connects this practice with explicit learning guarantees.

Our main contribution beyond this earlier work is showing that numerical and discrete traces can lead to very different learning problems. Earlier work shows how observing intermediate computations can make learning easier. Theorem 4 shows that observing every activation sign or hardmax route may still leave learning hard. In our construction, these signs or routes can be computed from the input without knowing the target; the information about the target is carried by the hidden numerical states. Learning actually remains hard even when the trace is available at prediction time. By contrast, Corollary 1 gives polynomial-time learning for ReLU networks when numerical activations are available during training. Corollaries 2 and 3 show when partial traces do suffice, giving fixed-depth learning guarantees from signs and attention traces alone.

W2. Claims exceed the supporting evidence. ... + Q2. Which upper and lower bounds match ...

A2. We will revise this wording. We used “tight characterizations” to describe our positive and negative computational results, so we will replace the phrase with “constructive learning guarantees and complementary hardness results.” Theorem 4 rules out a general polynomial-time learner, but does not match the precise exponential dependence of our algorithms. The intended meaning was that we provide a lower and an upper bound on what is possible in this setting

Q3. Can you identify a nontrivial deep-network family for ...

A3. Yes. One example uses repeated applications of the tent map

T(t)=2t−4(t−12)+.T(t)=2t-4(t-\tfrac12)_+.

Consider p≥4p\ge4 routes, each with an unknown unit vector ai∈Rpa_i\in\mathbb R^p. The input specifies a route ii and a vector zz, encoded as x=(ei⊗z,ei)x=(e_i\otimes z,e_i), and the target is

f(x)=TL(ai⊤z),L=⌊log⁡2p⌋,f(x)=T^L(a_i^\top z),\qquad L=\lfloor\log_2p\rfloor,

where TLT^L denotes repeated composition. This has a width-3p3p, depth-LL bias-free ReLU implementation. Each iteration adds another fold, giving 2L2^L linear pieces; the deeper gates are not halfspaces in the original input.

Assume ∣z∣≤2\\|z\\|\le\sqrt2 and t=ai⊤z∈[0,1]t=a_i^\top z\in[0,1] satisfies

t,\\{j/2^L:0\le j\le2^L\\} \right)\ge2^{-L-3}.$$ This retains three quarters of the projection interval and allows continuous input variation within each route. For this construction, the canonical readout coefficients and normalized gate margins give $$B=O(p^{7/2}),\qquad \gamma^{-1}=O(p^3).$$ Our bounds are exponential in depth and become polynomial in $p$ at the logarithmic depth specified above. Meanwhile, the full path dimension is $d(3p)^L=p^{\Theta(\log p)}$, where $d=p^2+p$. Theorem 5 therefore gives a polynomial-time guarantee without constructing the superpolynomial path representation used by the generic learner in Corollary 2. The route is visible, so this is a structured example. It gives a concrete nonlinear family satisfying the theorem's assumptions at logarithmic depth. We will include the explicit network construction and proof of these bounds. For the parity experiments, we have not established that both parameters are polynomially bounded. Those experiments test the benefit of intermediate supervision for the specified training procedure; they do not verify Theorem 5's assumptions. We will make this distinction explicit. **Q4. Are the length-generalization protocols in the main text ...** **A4.** Yes, these are separate experiments, but using the same implementation and training procedure. Figure 1b trains at length 16 with 128 examples and evaluates without retraining up to length 4,096. Appendix H's Figure 3 and Table 3 report the additional experiment trained at length 512 with 2,048 examples. The omission is that Appendix H documents the latter experiment without separately describing the Figure 1 runs. We will add the missing protocol and numerical results, and explicitly distinguish the two experiments in the text and captions.

Comments on the paper

1 comment

Dear Reviewers and ACs,

We would like to thank both reviewers for their effort in reviewing our paper and for their feedback which helped us improve the paper. We hope our responses have addressed their concerns. We would also like to briefly highlight what we see as the main strengths of our work:

  • A timely question. We study whether intermediate supervision changes the computational complexity of learning. Reviewer ku5W calls it “a very well-posed timely question” and our model “natural.”

  • A clear separation. Numerical hidden states make ReLU networks efficiently learnable (Corollary 1), while full sign or attention traces can still leave learning hard (Theorem 4). Reviewer 6bwq highlights this as the paper’s clearest conceptual contribution.

  • Soundness. Neither reviewer raised a correctness concern.

In our rebuttal, we addressed the main concerns: we will add and discuss the related work suggested by Reviewer ku5W, tone down the “tight characterizations” wording, and clarify the experimental protocol. All of these are presentation issues that can be fixed in the camera-ready version.

As we noted earlier, our submission received only two reviews. We hope this will not significantly affect the evaluation of our work, and we remain happy to clarify anything further if needed.

Best regards, The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.