acceptodds
Withdrawn from ICLR 2027

Generalised Rules from Compositional Structure

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Learning reusable components from complete-task answers is a central challenge in compositional generalisation. Understanding failures requires distinguishing what training examples reveal from whether learners can use that information. We study this distinction in finite-group compositions with independently hidden input and output meanings. By varying selected input around an anchor, we construct complete-task examples that provably determine the entire rule and enable an exact reconstruction algorithm. These examples also improve neural generalisation over equally sized random datasets with matching answer frequencies. Even when the target is expressible, comparisons of neural, discrete and constructive learning on identical sufficient examples show substantial differences. To investigate the remaining learning difficulty, we derive a cancellation law showing how joint uncertainty in component meanings suppresses input-dependent predictions. Together with matched interventions, these findings suggest that compositional generalisation depends on both the structure revealed by training examples and the learner's ability to coordinate component meanings.

Primary area:
interpretability and explainable AI
Keywords:
compositional generalisation, identifiability, algebraic structure learning, symbolic learning, data selection

Reviews

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

The submission attempts to study under which circumstances learning from compositional tasks can identify the meaning of underlying constituents.

Critical strengths

None

Critical weaknesses
  • The whole submission reads like an extremely jargon-heavy stream of thought without a clear motivation for why things are done.
  • It is unclear what significance the bespoke models, tasks and results have. They are defined in this work without clear motivation or reference to prior work
Questions for authors

We then give the same examples to the neural and discrete learners, enabling controlled comparisons when the examples determine the target function and both models can express it. In the 36-task study, the discrete learner achieves approximately 90% accuracy on unseen combinations, compared with 28% for the neural composer. Additionally, the structured examples improve neural generalisation by approximately 16 percentage points over equally sized random sets with matching answer frequencies. These results establish a replicated benefit from training example structure and substantial differences in how learners exploit sufficient information under their respective fixed budgets.

This section in the introduction is a good example of the poor structure of the paper. It is unclear to me why detailed results are presented in the introduction before the necessary context to understand them is provided.

Near uniform input and output dictionaries, we prove that input-dependent prediction differences require deviations in all dictionaries, giving a first possible term of degree p + 1 for p input positions. This cancellation law motivates removing uncertainty in individual dictionaries.

Another section of the introduction that illustrates the dense, jargon-heavy language used throughout the manuscript that I could barely comprehend.

The operation table is encoded by the fixed tensor Trsc = 1[r ⊕ s = c].

This is an example of heavy mathematical formalism to express simple objects (a binary table?) that makes it hard to understand what is being done.

Sufficiency concerns the input-answer function, so different dictionaries may still represent that same function.

If the inputs are different it is a different function. Maybe the mathematical concept missing here is an isomorphism?

A soft neural composer receives the correct composition table and learns probabilistic dictionaries through gradient training, while a discrete learner uses the same table and searches directly over one-to-one dictionaries. A constructive recovery learner infers an executable rule from selected complete-task answers without receiving the latent table

Why are these models chosen? How do they related to prior work?

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

This paper studies compositional generalisation in finite-group tasks with independently hidden input and output dictionaries. It develops an ordered factorisation and a constructive algorithm that exactly recovers the target function from selected complete-task answers, yielding provably sufficient training sets. Experiments show that these structured examples improve neural generalisation over size- and answer-frequency-matched random data, while substantial performance gaps remain between constructive, discrete, and neural learners. The paper also analyses how uncertainty in symbol meanings weakens learning signals, and tests three ways to help learning: revealing some true symbol mappings, requiring each dictionary to map symbols one-to-one, and providing correct answers for intermediate computations.

Critical strengths

The anchor-centred recovery construction is a clear and potentially useful contribution. It demonstrates, by means of an explicit construction, that the function F can be uniquely determined from its values on a sufficiently small subset alone. This yields a valuable lower bound.

The paper makes a valuable conceptual distinction between sufficient supervision and successful optimisation. The use of identical sufficient examples for constructive, discrete, and neural learners, together with training accuracy and held-out accuracy, is a good framework for diagnosing where compositional learning fails.

The authors' experimental design is extensive in scope, encompassing a diverse range of structurally distinct Abelian groups, non-commutative groups, and even non-associative groups, thereby endowing the phenomena revealed in the paper with greater universality.

Critical weaknesses
  1. The boundaries of contributions are unclear. By comparing three different optimisation methods, the authors obtain extensive experimental tables, and the results show that both constructive recovery and the discrete learner outperform the neural network. However, the authors neither reveal nor discuss what implications this has for training neural networks. Nor do they demonstrate whether similar combinatorial/discrete methods can replace fully connected neural networks in traditional symbolic regression tasks (such as modular addition arithmetic /arithmetic with carrying)

  2. Although the constructive approach can be proven sufficient, the training sets generated using this method give the constructive recovery learner an almost inherent advantage, making the subsequent comparative experiments less convincing. However, when the training set is randomly sampled (as a subset of GpG^p ), choosing F(a,a,a)F(a,a,a) does not guarantee that all F(x,a,a)F(x,a,a) are available. What would be the outcome of comparing the results of several algorithms under such condition?

  3. In Section 3.3, the authors devote considerable text to emphasising the importance of training set sufficiency, but they do not provide an algorithm for assessing whether a randomly generated training set satisfies this condition. Readers would also expect to know approximately how likely such a subset is to satisfy the condition when random sampling is performed with a sample size of 1≤x≤qp1\le x\le q^p.

  4. It is unclear that the neural network with externally injected group structure employed in Section 3.4.1 possess research significance and application value. According to the results reported in the paper, even when the group operation is explicitly provided, they do not exhibit any advantage.

Questions for authors
  1. How can the rationale behind the discrete learner be explained? I do not believe that this problem has local optimality. Your mappings are all Latin. When the other mappings are held fixed, even if the first dictionary is entirely correct, you may well obtain a score of zero if the subsequent assignments are incorrect. Therefore, maybe I misunderstand this algorithm.

  2. What do the "structured examples" mentioned in Sections 5.2 and 5.3 refer to? If they refer specifically to the construction in Section 5.1, how do you address the second point in the weaknesses?

  3. When the training set is randomly generated, how can one determine whether a given training set is sufficient (or sufficient with high probability) ?

  4. According to the argument in Section 5.4, increasing the arity p would have disastrous consequences. Why not consider only the case p=2, and how does the neural network method perform in this case? Could you report its performance across different group structures?

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

The authors consider group composition problems where the group operation itself is known but the input and output dictionaries need to be learned. They present a set of learning algorithms for such problems. They then characterize the number of samples necessary to learn these dictionaries and analyze the set of training examples necessary to learn the structure.

Critical strengths

The question the authors consider is interesting and the authors provide insight into the required set of input-output mappings to align a given format with an underlying backbone.

Critical weaknesses
  • My primary concern is clarity, which makes evaluating some of the paper fairly difficult for me. Much of the results section is lacking detail that made it difficult for me to understand what exactly was being done. I was unable to find these details in the appendix as well (though it is possible I missed them). I am highlighting instances of this below, to illustrate my concern and hopefully better understand the results during the discussion:
    • Which learner are you evaluating in section 5.2? You are introducing three learners but then only discussing "the learner".
    • In what context is table 1 relevant? I assume section 5.1, but you are never actually referencing it in the text. I also could not find a definition for "full slice" or "sparse queries" --- I assume sparse queries might be the algorithm from Section E.1?
    • In Theorem 2, what is "input-dependent prediction variation" and what are the "Paths towards the correct dictionaries" and what does it mean for them to "attain these orders"?
    • I would also note that the proofs seem to be distributed across multiple sections of the appendix. E.g., the proof of Theorem 3 is distributed over Appendix E and F without ever making clear specifically which steps are a part of the proof. I would strongly suggest having a dedicated section for each theorem that you prove.
  • I think the motivation could be a bit stronger/clearer. Isn't learning the group operations themselves often the challenging aspect? What situations are you thinking about when holding them fixed? Do you think of the learners you introduce here as potential learning algorithms you use in practice?
Questions for authors

Please see my questions under weaknesses. I am unable to recommend acceptance for the paper as is but am looking forward to the discussion period.

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

Related papers

Discussion (0)

Sign in to comment.