← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

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

  1. 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.

  2. 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.

  3. 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.