Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

Bochen Lyu; Xiaohao Cai; Yiyang Jia; Zhanxing Zhu

REVIEW 3 major objections 5 minor 1 cited by

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A one-layer transformer provably learns k-sparse Boolean functions — parity, AND, and OR — through either RL or SFT, with RL acquiring the entire chain of thought in a single gradient update while SFT learns it step by step.

desk verdict Worth a serious referee; the RL half is proved for an immediate-reward surrogate, not the stated policy gradient, so the RL-vs-SFT contrast needs re-scoping. read the letter →

arxiv 2511.17852 v3 pith:37I6P3OY submitted 2025-11-22 cs.LG stat.ML

Bochen Lyu , Yiyang Jia , Xiaohao Cai , Zhanxing Zhu This is my paper · ORCID

classification cs.LGstat.ML MSC 68T0768Q32

keywords chain-of-thoughtRLfine-tuningSFTwithoutteacherforcingk-sparseBooleanfunctionsparitypolicygradientprovablelearningtransformerattentiondynamics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that a one-layer transformer, fine-tuned either by reinforcement learning with per-step process rewards or by supervised fine-tuning without teacher forcing, provably learns k-sparse Boolean functions — parity, AND, and OR — when the task is decomposed into a chain of 2-input reasoning steps. Both guarantees rest on a single sufficient condition: the separation of the critical gradient component, meaning that at initialization the gradient is strictly larger at the two child positions each reasoning token should attend to than at every other position. Under that condition, RL reaches epsilon-accurate attention weights after one sign-policy-gradient update, so the whole chain of thought is learned at once, while SFT needs one update per chain level because later ground-truth labels are usable only after earlier generated steps are correct. If true, this converts an empirical contrast between RL and SFT into a sharp statement about learning dynamics, and it isolates the reward design and the absence of teacher forcing as the deciding factors.

What carries the argument

The critical gradient component, γ^p_{l(t)}(y^{(t−1)}) = (2/(k−1)) ψ′(ξ_{l(t)}) φ₂(y_{i₁}, y_{i₂}) y_p, is the building block of both the policy gradient and the SFT gradient: each gradient entry factors as (γ_p − Σ_i γ_i σ_i) σ_p, so at the all-ones initialization its sign is determined by whether p is one of the two child nodes the current reasoning token must attend to. The 'separation' of this component — strictly larger at child positions than at all other positions — is the sufficient condition driving both theorems. Supporting machinery consists of causal plus 'pretrained' masks on the attention matrix W, which force step-t tokens to attend only to step-(t−1) tokens, and activation fu

What would settle it

On a small parity instance (say d=8, k=4), compute at initialization W=1 the full policy gradient of Eq. (8) including the future-reward terms, and compare the sign pattern of its attention entries with the sign pattern of the immediate-reward gradient in Eq. (9). If any child position loses its strictly positive sign relative to every non-child position, the one-update guarantee does not extend to the stated objective R(W), and the 'entire chain at once' conclusion holds only for the immediate-reward surrogate.

Watch

Extended reading notes

Core claim

On the paper's own terms: fine-tuning a one-layer transformer on the intermediate steps of a recursively decomposed sparse Boolean function succeeds under one sufficient condition, the separation of the critical gradient component. Theorems 3.1 and 3.2 show that when this condition holds, sign-policy-gradient RL reaches ∥softmax(W(1))−softmax(W*)∥₁ ≤ ε after a single update, and sign-gradient SFT reaches the same error after T updates, where T is the length of the reasoning chain. The paper verifies the separation condition for k-PARITY, k-AND, and k-OR with specially chosen activation functions, and proves a hardness result: RL with only a final reward fails for sparse parity because the po

Load-bearing premise

The RL theorem is proven for a truncated gradient (Eq. 9) that keeps only the immediate reward at each step, and the paper asserts, without derivation, that this equals optimizing RL with immediate reward; if that assertion fails, the one-update result applies to a greedy per-step objective rather than to the stated reward R(W).

Editorial extensions

If this is right

If the separation condition holds, RL with per-step process rewards makes the transformer reach ε-accurate attention weights after a single sign-policy-gradient update, meaning the entire chain of thought is absorbed at once (Thm. 3.1).
SFT without teacher forcing needs exactly T sign-gradient updates, one per chain level, and this stepwise behavior is intrinsic to the objective rather than imposed by a curriculum (Thm. 3.2).
For sparse parity, RL with only a final reward is hard in this framework: the policy-gradient variance over the exponentially many candidate parity functions drowns out the target's signal (Prop. 3.1).
Both guarantees are powered by the same separation condition, so whenever SFT succeeds the corresponding RL variant also succeeds; the shared bottleneck is whether the initial gradient distinguishes child positions from non-child positions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's RL result is proven for the update in Eq. (9), which drops the future-reward terms of the full policy gradient in Eq. (8); the text asserts without derivation that this is 'equivalent to optimizing RL with immediate reward.' If that equivalence fails, the one-update claim describes a greedy per-step reward algorithm, and the RL-versus-SFT contrast becomes a comparison between two diffe
A testable prediction follows for real reasoning models: with process-reward RL, per-step accuracy across the chain should improve simultaneously, whereas with SFT it should improve sequentially from the first step to the last — measurable by logging per-step accuracies during fine-tuning.
The separation condition is verified only for the three chosen activations ψ; for other k-sparse decomposable functions it may fail, so the paper delineates a class of CoT-friendly reasoning problems rather than establishing universal learnability.
The proofs are population-level statements; the authors list finite-sample analysis as future work, and sampling noise is the most immediate threat to the clean sign separation on which the one-update and T-update guarantees rely.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The thing to know: this is a genuine extension of the Kim–Suzuki line, with a clean toy setup and a useful observation about reward granularity. The catch is that the RL result is proved for a truncated gradient that the paper asserts—without proof—is equivalent to the actual policy gradient. That assertion is doubtful, and until it is resolved the “RL learns the whole chain in one update” claim describes a hand-modified objective, not vanilla REINFORCE on the stated process-reward R(W).

What is new and good: removing teacher forcing from SFT is a real relaxation, and the parity dynamics in Theorem 4.1 are a genuinely closed-form characterization. The one-update RL versus T-update SFT contrast is novel and conceptually interesting, even if it ends up being a claim about an immediate-reward objective rather than about RL as usually understood. The separation conditions are explicit and the parity verification is the strongest part. The AND/OR section is weaker—Claims with case analysis, relying on positive probability masses for quantities like b and c—but not obviously wrong. The citation pattern looks appropriate; prior work is squarely acknowledged.

Soft spots, in proportion: the Eq. (8)-versus-Eq. (9) issue is the load-bearing one. In REINFORCE, the log-derivative at step t is multiplied by the sum of rewards from t onward. The paper keeps only r_t and says this is “equivalent to optimizing RL with immediate reward.” That is not derived, and in general it is false: r_{t+1} depends on y(t), so the omitted terms generically have nonzero expectation. The theorems and the parity dynamics are all proved for this truncated estimator. This is an internal-consistency problem, not a disagreement with prior consensus, but it means the headline contrast is between a greedy per-step reward and SFT, not between two standard training objectives. The other limitations—hard masks as a stand-in for pretraining, activation functions chosen per target function, population gradients, no code or data—are real but secondary; they are the price of tractability and are stated plainly in the paper.

Who this is for: theorists working on transformer training dynamics and CoT, and anyone who wants a concrete model of how reward design changes learning order. I would send it to a serious referee; the gap is fixable and the contribution is worth the referee’s time. If the authors either prove the omitted terms vanish or explicitly redefine the RL objective as immediate reward, the paper can be accepted with moderate revisions.

Referee Report

3 major / 5 minor

Summary. The paper studies a one-layer transformer with positional encoding, softmax self-attention, and a feedforward layer, fine-tuned by either RL (sign policy gradient) or SFT without teacher forcing, to learn k-sparse Boolean functions that are recursively decomposable into fixed 2-sparse Boolean functions. A hard mask is imposed on the attention weights, called a 'pretrained mask', to encode the recursive decomposition. The authors define a process reward, derive its policy gradient, and then state that optimizing with a truncated immediate-reward version is equivalent; under a separation condition on a 'critical gradient component', they prove that RL learns the entire chain in one update (Theorem 3.1), while SFT learns one step per update (Theorem 3.2). They verify the separation condition for k-PARITY, k-AND, and k-OR, and give exact attention dynamics for parity (Theorem 4.1). They also prove a hardness result for RL with only a final reward (Proposition 3.1). Numerical experiments on k-PARITY illustrate the claimed sign patterns.

Significance. If the results are correct, this is a valuable contribution: it provides one of the first theoretical analyses comparing RL and SFT for chain-of-thought fine-tuning in a tractable transformer model, with explicit separation conditions, closed-form dynamics for parity, and a negative result for final-reward RL. The paper is honest about its limitations (population gradient, hard-mask pretraining, one-layer model), and the parity analysis in Section 4.1 is concrete and checkable. The main conceptual claim — that RL learns the whole reasoning chain simultaneously while SFT learns it step by step — is interesting and empirically supported by the sign-pattern plots in Appendix D. However, the central derivation of the RL update is currently not rigorous, and the AND/OR verification is incomplete, so the significance of the main comparison is not yet fully established.

major comments (3)

[Sec. 3.1, Eq. (8) vs Eq. (9)] The gradient used in Theorem 3.1 is not the policy gradient of the stated objective R(W). Lemma 1 correctly gives Eq. (8) with cumulative future rewards Σ_{τ≥t} r_τ. The text then asserts without proof that Eq. (9), which multiplies by only r_t, 'is equivalent to optimizing RL with immediate reward.' This equivalence is not generally true: r_{t+1} depends on y(t), so E[∇ log p(y(t)|y(t−1)) r_{t+1}] is generically nonzero. Because Theorem 3.1 and Theorem 4.1 analyze Eq. (9), the results establish learnability for a truncated immediate-reward estimator, not for vanilla policy gradient on the process-reward objective R(W) claimed in the introduction. This undermines the headline claim that 'RL learns the whole CoT chain in one update' as a statement about standard policy gradient. The authors must either prove that the omitted future-reward terms vanish at the relevant iterates (which is un
[Thm 3.1 proof, around Eq. (45)] The proof of Theorem 3.1 asserts that 'W⋆ = arg max_W R(W) has the formulation' with attention scores 1/2 on relevant positions and 0 on irrelevant positions. This is not proven. The objective R(W) may have multiple global optima, and even if the ideal attention pattern is one of them, the error bound ∥softmax(W(1))−softmax(W⋆)∥₁ is only meaningful if W⋆ is that particular pattern. Please either characterize all global optimizers of R(W) and prove the ideal pattern is a global optimizer, or define W⋆ explicitly as the ideal attention matrix and prove the corresponding bound. As written, the theorem's conclusion is not justified.
[Claim 4.2 and App. C.3.1, Eq. (127)] The verification that k-AND (and k-OR) satisfy the separation condition reduces to ∆ ∝ 8b > 0 (or ¯∆ ∝ 8c > 0), where b and c are sums over case-split regions D_{-1} and D_{+1}. The proof simply states that b > 0 (c > 0) without proving that these terms are strictly positive. With ψ(z) = max(z,0) for AND, p_+ = ψ(ξ) can be zero when ξ ≤ 0, and the sets D_{-1}/D_{+1} can be empty under the current policy. Therefore the separation condition is not rigorously established for all relevant cases. A complete case analysis, or additional assumptions on the initialization and the distribution of ξ, is needed before Claim 4.2 can be accepted.

minor comments (5)

[Abstract / Definition 2.1] The abstract says 'k-sparse Boolean functions that can be recursively decomposed into fixed 2-sparse Boolean functions,' but the paper assumes k = 2^T. Please state this explicitly in the abstract or in Definition 2.1, as it restricts the class.
[Sec. 2.2, Eq. (4)] The notation in the mask definition is hard to parse: t is used both for the index of the reasoning step and for a loop variable in the same sentence ('givent∈[T]' and 'ift= 1'). Please clarify the indexing, perhaps by using different symbols for the step index and the row index.
[App. A.2, around Eq. (27)] In the proof of Lemma 2, the factorization p(y(t:)|x) = p(y(t:)|y(t−1)) is used; this relies on the pretrained mask making y(t) depend only on y(t−1). The independence of tokens within y(t) is also used implicitly. A short justification of these factorizations would improve readability.
[Sec. 4.1, Eq. (16)] The notation 'dt−1−2' is ambiguous: it should be d_t − 1 − 2 or d_{t-1} − 2? Please disambiguate with parentheses or typeset clearly. Similar notation appears in several equations in the appendix.
[App. D] The numerical experiment uses 50,000 samples but reports no confidence intervals or multiple seeds. Since the plots are meant to support the theoretical sign-pattern claims, a few independent runs or an explicit statement that the sign pattern is deterministic under the analytic gradient would strengthen the evidence.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theorems are conditional on an explicit separation condition, verified by direct calculation for the worked examples.

full rationale

The paper's central derivations are self-contained conditional statements rather than fitted predictions. Theorem 3.1 assumes the separation of the critical gradient component (Eqs. 10-11) and derives, via Lemma 2, that sign policy-gradient updates on the explicitly stated estimator Eq. (9) increase relevant attention weights and decrease irrelevant ones; the proof is algebraic and does not reuse the conclusion. Theorem 3.2 is analogous. The applications in Section 4 do not assume learnability: for k-PARITY (Theorem 4.1), k-AND, and k-OR (Claim 4.2), the separation inequalities are checked by explicit expectations, and the activation functions are stated as designed choices (Table 1) rather than fitted to the target result. There is no parameter fitting to data and no renamed empirical pattern being presented as prediction; the numerical section is illustrative. The only in-scope issue I flag is one of internal consistency, not circularity: after Eq. (8), the text says 'we consider optimizing max_W R(W) with the policy gradient below, which is equivalent to optimizing RL with immediate reward,' and Eq. (9) drops the future-reward terms from the REINFORCE gradient. That equivalence is asserted without proof and is not evidently true as stated. However, Theorem 3.1 is explicitly stated and proved for the sign of the Eq. (9) estimator, so the paper does not secretly substitute the conclusion of the theorem. The one self-citation (Lyu et al. 2025) appears only among several references for an architectural tractability choice and is not load-bearing. The hand-designed masks and activations are disclosed as structural priors/designed expressibility choices, not as independently fitted inputs, so they do not make the derivation circular. No circular step can be exhibited from the paper's own equations.

Assumptions & free parameters 0 free parameters · 8 assumptions · 1 invented entities

The central results rest on a heavily specified toy model: fixed tree recursion, hard-coded level masks, per-function activations, population sign-gradient updates, and exact intermediate supervision. The paper contributes the separation-condition proof technique and verifies it on three examples, but these structural choices are assumed rather than derived.

assumptions (8)

domain assumption Input x is uniform over {±1}^d, coordinates are independent, and the support B is fixed.
Used throughout Def. 2.1 and all expectation computations, e.g., E_x[x_i]=0 and independence of coordinates in Lemma 5 and Appendix C.
domain assumption The target k-sparse function has k=2^T and decomposes into a complete binary tree of fixed 2-sparse Boolean functions.
The whole CoT construction, the number of SFT updates T, and the mask structure depend on this exact recursion.
ad hoc to paper The model is the specific one-layer transformer of Sec. 2.2: merged key-query matrix, value matrix preserving only x, no residual, and causal mask plus Eq. (5).
The proofs are tied to this exact architecture; it is not justified as an approximation to standard transformers.
ad hoc to paper The hard mask in Eq. (4) encodes which level of the tree each token belongs to and is called 'pretraining'.
The mask gives the model the recursive level structure for free; the paper admits this is a heuristic structural prior, not learned pretraining.
ad hoc to paper The activation function ψ is chosen per target function (Table 1) so that the expressibility condition Eq. (73) holds.
Learnability for AND and OR depends on these specific ReLU/min variants; the model is not generic across activations.
ad hoc to paper Optimization is population sign-gradient descent with W(0)=1 and η=Ω(ln(d/ϵ)).
All theorems are for this specific optimizer; no finite-sample or stochastic-gradient analysis is provided.
ad hoc to paper The RL update uses the immediate-reward policy gradient in Eq. (9), dropping future-reward terms from Eq. (8).
Sec. 3.1 asserts this is equivalent to immediate-reward RL without a derivation; the theorem proves learnability for this modified update.
domain assumption The separation of the critical gradient component holds for the functions considered.
For parity this is proven as Theorem 4.1; for AND and OR it is argued in Claim 4.2 and the appendix. For general k-sparse functions it remains a sufficient condition.

invented entities (1)

Hard 'pretrained' mask (Eq. 4)
purpose: Inject the recursive-decomposition level structure into the attention pattern so that each CoT step attends only to the previous level.
No learning or pretraining produces this mask; it is a hand-designed prior and would not transfer to unseen decompositions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently." pith.science (2026). https://pith.science/paper/37I6P3OY

@misc{pith2026251117852,
  author       = {Pith},
  title        = {Pith review of: Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/37I6P3OY}},
  note         = {Machine review of arXiv:2511.17852}
}

abstract

Transformers can acquire Chain-of-Thought (CoT) capabilities to solve reasoning tasks via fine-tuning. Reinforcement learning (RL) and supervised fine-tuning (SFT) are two primary approaches to this end. In this work, we examine RL with verifiable process rewards and SFT for learning $k$-sparse Boolean functions with a one-layer transformer through intermediate reasoning steps akin to CoT. In particular, we consider Boolean functions that can be recursively decomposed into fixed 2-sparse Boolean functions. We first analyze the learning dynamics of RL fine-tuning with verifiable process rewards and SFT in a unified way, allowing us to identify sufficient conditions under which the transformer provably learns these functions. We then verify that the conditions hold for three examples, including $k$-PARITY, $k$-AND, and $k$-OR, thus demonstrating their learnability via both RL and SFT. Notably, we reveal that RL and SFT exhibit distinct learning behaviors depending on supervision: RL learns the whole CoT chain simultaneously, whereas SFT without teacher forcing learns the CoT step-by-step. Overall, our findings provide insights on the mechanisms underlying RL and SFT and how they differ in triggering the CoT capabilities of transformers, and suggest that the comparison between RL and SFT should consider the intermediate supervision.

Figures

Figures reproduced from arXiv: 2511.17852 by the authors.

**Figure 1.** (a) Recursive decomposition of learning a k-sparse Boolean function Φk(x) with a random set B ⊆ [d] (shaded boxes in the lowest level) into solving sub-tasks by following a reasoning chain (bottom to top). Each level of the binary tree corresponds to a step of the reasoning chain, where each node in a level computes a 2-sparse Boolean function ϕ2(·, ·) over its two child nodes. (b) The self-attention weight W with d… view at source ↗

**Figure 2.** The pretrained transformer iteratively uses its output to solve [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** (a) The ground truth (σ ⋆ ) Nt−2+p Nt−1+l (t) . Each white box is 0.5 and each gray box is 0. (b) sign(∇W L(W)) at W(0) = 1. Each white box has value +1 and each black box has value −1. Gray boxes have value 0 coming from causal mask and pretrained mask. 41 [PITH_FULL_IMAGE:figures/full_fig_p041_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: sign(−∇W L(W)) computed by W(s) for different updating step s. Each white box has value +1, each black box has value −1, and grey boxes are 0. 42 [PITH_FULL_IMAGE:figures/full_fig_p042_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
cs.LG 2026-02 unverdicted novelty 8.0 of 10

RLVR training on transformers for compositional tasks follows an implicit curriculum from easy to hard problems, with difficulty spectrum smoothness determining steady relay progress or grokking phase transitions.

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.