{"id":"6025f12e-ac6a-4cd4-9973-3c96b0dbe231","arxiv_id":"2511.17852","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.","lead":"The paper proves that a one-layer transformer can learn certain sparse Boolean functions when fine-tuned by reinforcement learning or supervised fine-tuning, provided the model is given hand-designed masks and task-specific activations. It identifies a claimed behavioral difference: RL updates the whole reasoning chain at once, while SFT learns it step by step.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1 analyzes Eq. (9), a truncated immediate-reward gradient, not the policy gradient of R(W) in Eqs. (7)-(8); the asserted equivalence is unproven and the omitted future-reward terms are generically nonzero.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Eq. (9) is asserted, not derived, to be equivalent to optimizing the stated RL objective. This is the point on which the central claim 'RL learns the entire CoT chain in one update' rests. The full policy gradient in Eq. (8) includes future rewards in the gradient of earlier actions; Eq. (9) drops them. Because r_{t+1} depends on y(t), the dropped terms are not obviously zero, so the proof may establish learnability only for a modified immediate-reward estimator. This does not automatically falsify the mathematical results for Eq. (9) or the SFT theorem, but it does compromise the paper's interpretation as a comparison between RL and SFT under standard policy-gradient optimization. A concrete computation of the full gradient at initialization can settle the issue. If the signs match, the concern is resolved and the verdict could be strengthened; if they differ, the theorem statement and the behavioral contrast should be revised or explicitly restricted to the truncated estimator.","tokens_in":70868,"tokens_out":6462,"duration_ms":64162,"concrete_test":"At W(0)=1 for k-PARITY (e.g., d=20, k=16), compute the population full policy gradient Eq. (8) for a relevant position p of y(1), including the omitted future-reward term E[grad_{W_{p,l}} log p(y(1)_l|x) r_2(y(2),y(1))], and compare its sign with the truncated Eq. (9). If the sign of any relevant position flips or becomes zero, Theorem 3.1 holds only for the truncated estimator; if all signs match, the equivalence is at least numerically true at initialization and the concern is mitigated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is that the RL result is proved for a gradient that is not the policy gradient of the stated objective. The paper defines R(W)=E_x E_{y~p_W}[sum_t r_t(y(t),y(t-1))] and correctly derives the REINFORCE gradient in Eq. (8): the gradient w.r.t. log p(y(t)|y(t-1)) is multiplied by sum_{tau>=t} r_tau. Theorem 3.1 then switches to Eq. (9), which multiplies by only r_t. The sentence asserting equivalence to 'optimizing RL with immediate reward' is not a proof, and the equivalence is false in general: r_{t+1} depends on y(t), so E[grad log p(y(t)|y(t-1)) r_{t+1}(y(t+1),y(t))] is generically nonzero. Unless the omitted terms are shown to vanish at W(0)=1 for parity/AND/OR, the sign pattern used in the proof of Theorem 3.1 is the sign of a different estimator, not the sign of grad_W R(W). Consequently, the headline 'RL learns the whole CoT chain in one update' may describe a hand-modified immediate-reward surrogate rather than vanilla policy gradient on the stated process-reward objective; the RL/SFT contrast would then be between two differently engineered objectives. This is an internal-consistency issue rather than a dispute with prior consensus.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":71306,"tokens_out":7496,"duration_ms":71387,"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":[{"comment":"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","section":"Sec. 3.1, Eq. (8) vs Eq. (9)"},{"comment":"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.","section":"Thm 3.1 proof, around Eq. (45)"},{"comment":"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.","section":"Claim 4.2 and App. C.3.1, Eq. (127)"}],"minor_comments":[{"comment":"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.","section":"Abstract / Definition 2.1"},{"comment":"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.","section":"Sec. 2.2, Eq. (4)"},{"comment":"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.","section":"App. A.2, around Eq. (27)"},{"comment":"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.","section":"Sec. 4.1, Eq. (16)"},{"comment":"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.","section":"App. D"}],"recommendation":"major_revision","confidential_remarks":"The paper has a valuable core: the parity analysis is concrete, and the step-by-step SFT induction is a nice contrast. However, the RL result as stated is not about the stated policy-gradient objective, and the AND/OR verification is incomplete. If the authors rework the RL section to either prove the omitted terms vanish or honestly define an immediate-reward objective, and if they complete the positivity arguments for AND/OR, the paper could become publishable. The central conceptual claim—'RL learns the whole chain in one update'—currently depends on the truncated gradient, so the framing needs substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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).\n\nWhat 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.\n\nSoft 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.\n\nWho 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.","headline":"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.","tokens_in":71683,"tokens_out":2085,"would_cite":true,"duration_ms":23450,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["chain-of-thought","RL fine-tuning","SFT without teacher forcing","k-sparse Boolean functions","parity","policy gradient","provable learning","transformer attention dynamics"],"falsifier":"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.","tokens_in":70721,"feed_emoji":"🧠","tokens_out":10119,"duration_ms":80826,"temperature":0.7,"pith_summary":"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.","feed_headline":"RL learns a reasoning chain in one update; SFT does it step by step","feed_subtitle":"Proof: per-step rewards fix all attention weights at once; supervised labels fix them one level at a time.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["RL learns CoT in one update; SFT takes one step per level","Proven: RL vs SFT — one-shot vs stepwise CoT learning","RL fixes all attention weights at once; SFT fixes them level by level","For transformers: RL learns reasoning in one go, SFT step by step"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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).","fun_headline_variants_meta":{"raw":{"variants":["RL learns CoT in one update; SFT takes one step per level","Proven: RL vs SFT — one-shot vs stepwise CoT learning","RL fixes all attention weights at once; SFT fixes them level by level","For transformers: RL learns reasoning in one go, SFT step by step"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3256,"prompt_tokens":796,"completion_tokens":2460,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":2388}},"tokens_in":540,"tokens_out":2460,"duration_ms":15935,"temperature":1.0,"reasoning_tokens":2388,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:51:42.366444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}