Generalised Rules from Compositional Structure

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.