Embeddings & representations · RL & post-training / Open question
Learning to Compose
Reasoning requires composing reusable operations, and final-answer feedback may fail to reveal the representations needed to learn those operations.
Seed catalog · Showing the bundled record.
Problem statement
Let tasks be depth-H expression trees generated by a finite grammar of K operations on S latent states, with observable terminal inputs and answers but unlabelled intermediate states. A shared finite-width neural policy learns both state embeddings and composition from binary final-answer reward. Characterize which grammar reachability, task-coverage and initial-success conditions permit learning unseen compositions in polynomial samples and computation, and give a hardness regime within the same grammar class.
Assumptions and scope
- Specify the grammar, depth, latent-subgoal access, base-policy probabilities and algorithm class; all polynomial factors must name their parameters.
- Reward only final correctness in the main model. Privileged intermediate labels define a comparison model, not a hidden premise.
- Compare with fixed-library reweighting and state which notion of transfer to unseen compositions is required.
What would settle it?
A necessary/sufficient or sharply separated learnability condition for the specified shared-representation class, with an algorithmic guarantee and a lower-bound construction.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Barzilai et al. already characterize learnability via a task-advantage ratio in their autoregressive model. The additional target is learned latent subgoals, shared representation and transfer beyond a fixed strategy library. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Barzilai, Wolf and Basri — When Is Compositional Reasoning Learnable from Verifiable Rewards? ↗partial theory · source checked 2026-11-19
Primary abstract checked: task-advantage-ratio characterization, positive learnability cases and suboptimal-composition obstructions. The remaining target must go beyond this specified autoregressive model.
- Cheng et al. — How RL Reshapes LLM Reasoning: Transferability, Coverage, and Scaling Laws ↗partial theory · source checked 2026-11-19
Full-text model and theorem statements checked: two-stage linear softmax policies with frozen features, realizability/orthogonality assumptions and gradient-flow limits. Coverage can change without new strategy support.
- Yang and Hu — Feature Learning in Infinite-Width Neural Networks ↗partial theory · source checked 2026-11-19
Abstract checked: feature-learning infinite-width parameterizations and tensor-program limits are existing results, not an open existence question.