acceptodds
Under review as a conference paper at ICLR 2027

Project Auto-World: Towards Automated Benchmarking of Neural Relational Reasoners

Abstract

Reasoning about relational structures remains a significant challenge for neural models, particularly when they must systematically apply learned knowledge to problem instances that are harder than those seen in training. Progress is hampered by the difficulty of evaluating such generalization, since a priori, it is rarely clear what makes an instance hard. We study how this issue can be addressed by using language models (LMs) to automate benchmark generation, learning to produce increasingly challenging instances in an end-to-end manner. Concretely, given a world parametrized by Datalog rules, and an Edge Transformer as the reasoning evaluator, we use LM-driven evolutionary search (based on FunSearch) and autonomous agentic search to discover sampling functions that yield hard problem instances. We also show that the Edge Transformer can be improved using this data such that it generalizes well to further data perturbations. Finally, we show that the same machinery can be applied to novel worlds proposed by LMs, opening the door to autonomous research on neural relational reasoning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
systematic generalization, graph neural networks, relational reasoning, large language models, automating scientific discovery

Reviews

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

The paper proposes an method to automatically generate to evaluate LLMs for relational reasoning even when it is not clear what makes problem instances hard. The method uses Edge Transformers with Datalog rules, performing evolutionary search to identify samplers that can generate challenging problem instances. It is demonstrated that training ET on generated hard examples enhanced their performance.

Critical strengths
  • The paper is well-written and easy to follow. It delivers important concepts on relational learning. The idea of automating the evaluation of relational reasoning is interesting and insightful.
  • The proposed framework is model-agnostic, and thus should transfer to different architectures. The samplers induced by LLMs successfully identify new forms of difficulty that cannot be explained via standard criteria such as inference depth. This demonstrates the practical efficacy of the proposed method.
Critical weaknesses
  • The framework aims at generating challenging tasks, but it only tests the models on small instances. It is noted in experiments that KGs contain at most eight entities. Real-world reasoning tasks typically involve with a large number of data. Thus a concern on the scalability remains.
Questions for authors
  • The system generates instances by deliberately search for ones where models get wrong. Would it be ensured that the method generates genuinely hard instances, rather than identifying mere bugs or blind spots for given models?
1 comment

The framework aims at generating challenging tasks, but it only tests the models on small instances. It is noted in experiments that KGs contain at most eight entities. Real-world reasoning tasks typically involve with a large number of data. Thus a concern on the scalability remains.

Our choice to generate small KGs is not a matter of scalability. It is straightforward to generate reasoning problems that are challenging for neural models, when the problems are allowed to be large. For instance, the NoRA 1.1 dataset was created by recursively expanding story graphs using a fixed set of templates. This makes it straightforward to generate problems with arbitrarily large OPEC values, which can reduce the accuracy of all existing models to practically 0. However, when models fail on small problems, it suggests that there is something fundamentally missing in their architecture or training data, which is precisely what we want to uncover. Note that reasoning performance on small KGs is also important for many applications (e.g. relation extraction in NLP, molecular property prediction).

The system generates instances by deliberately search for ones where models get wrong. Would it be ensured that the method generates genuinely hard instances, rather than identifying mere bugs or blind spots for given models?

In fact, finding “blind spots” for a given model is one of our main motivations, so we disagree that finding “mere bugs or blind spots” would be a weakness. However, our transferability experiments (e.g. Table 5) show that the learned priority functions transfer to other model architectures, and to some extent also to other rule bases, suggesting that they do capture general difficulty aspects, rather than model-specific artefacts.

Reviewer_YtmXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the automatic generation of small knowledge graphs designed to challenge neural relational reasoners. Specifically, it explores three LLM-based approaches to generating Python priority functions for scoring candidate edges: FunSearch-style evolutionary search, a Claude-based coding agent, and direct LLM dialogue.

Critical strengths

1.The problem is clear: systematic generalization cannot be evaluated unless one knows which graphs are hard, and random graphs rarely contain those structures. 2.The search target is automatically verifiable. Entailments come from Clingo, and fitness is model failure, so no human labels are required. 3.Three generators are compared with cross-evaluation. Table 1 shows that Claude samplers and evolutionary samplers hit different distributions, and four evolutionary seeds agree with each other. 4.Hardness transfers across architectures. In Table 4, models that score 0.44–0.72 on the NoRA training set fall near 0 on auto-research and evolutionary queries. 5.The SUPERET result has a control. Figure 3 shows that it resists later FunSearch rounds, while Table 2 shows that auto-research still drops it from about 0.86 to 0.57. The authors also report that the auto-research training set lacks diversity.

Critical weaknesses

1.“Novel difficulty” is mostly a residual. Table 3 trains a gradient-boosting classifier on depth, OPEC, and backtrack load, and the leftover McFadden pseudo-R² is high. Accuracy on these test sets is already very low, so those metrics have little variation left to explain. Adding entailed off-path edges reduces the unexplained score by less than 8 points. 2.Fitness and the reported metric differ. Equation (1) optimizes the minimum predicted probability of some true relation, estimated on only 8 graphs. The paper reports exact match over the full relation set. Search can win by breaking a single fragile label. 3.The hard instances look like a narrow distribution rather than a general difficulty axis. In Table 1, Claude samplers score 0.92–0.99 in-distribution and collapse under a different sampler. A model trained on auto-research data scores only 0.09–0.15 on every test column. 4.The initial Edge Transformer, and every later round, mixes NoRA’s test-D, test-OPEC, and test-BL into the 6,000 training queries. The model is not trained on the standard NoRA split, so comparisons with “beyond existing difficulty splits” are easy to misread. Iron Coast does not support a closed loop in which rules are also generated automatically. Most cross-accuracies in Table 6 are near 0, and the diagonal is empty. Two of the seven Claude samplers were dropped because they produced nonsensical worlds; the NoRA constraints themselves are incomplete. 5.The main tables have no training variance. Graphs have at most 8 entities, with the edge-to-entity ratio fixed at 2.5–3. Signals recovered by the agent include multi-hop chains and multiple relations on one entity pair; multi-hop depth is an existing metric.

Questions for authors

See weakness.

2 comments

W1

We provide entailed off-path edge count as an easy-to-understand example of a source of difficulty that we were unaware of before doing the experiments. The drop in the Unexplained score is indeed somewhat limited (albeit statistically significant). The analysis in Figures 10-13 provides some further insights (e.g. the fact that sampled graphs have a higher percentage of parallel edges and higher edge-label entropy than would be expected).

W2

The fitness function has two minima. The inner minimum encodes that all the labels have to be right for a query to be answered correctly, which is fully in line with our use of exact match as the evaluation metric. The outer minimum encodes that we want to have stories which admit at least one hard query (rather than stories for which randomly sampled queries are hard). While the evolutionary process could indeed, in principle, lead to solutions that target a specific hard-to-predict label, in practice this is not what is happening. This can be seen from the learned priority functions that are listed in the paper (which focus mostly on graph features) and from the fact that the learned priority functions to some extent transfer to other rule bases (see e.g. Table 5 and Figure 4).

W3

The fact that models trained using the Claude samplers collapse when tested on the evolutionary priority functions simply means that these latter generate different problem instances than the Claude samplers; not necessarily that they sample instances from a narrow distribution. Similar for the model trained on the auto-research priority function in Table 2. It is difficult to measure (or even define) whether the priority functions capture a general difficulty axis. However, the fact that the SuperET shows robust performance on a wide range of test sets suggests that the discovered priority functions generate examples that are sufficiently diverse.

W4

Regarding the first point, the mixing is by design since the goal is to discover difficulty axes that are orthogonal and different from the existing difficulty axes found in the NoRA data generating process. This data mix also includes the standard NoRA split.

Note that Iron coast is essentially the world rule set and we are looking at story instance generation given the fixed set of iron coast world rules. No new rule sets are generated during the training loop and only story instances with respect to discovered priority functions.

These Claude samplers were dropped since they do not satisfy canonical constraints of NoRA (e.g. locations cannot have family relations which should only be confined to persons) and post-selected. This choice has no bearing on the results and was originally enforced through hard programmatic filters in the NoRA sampler. Table 6 from the appendix is only meant to highlight the cross-world transfer learning ability of models across various samplers and just shows that the data discovered by CI-Atlas, CI-bw, Cw-hill are distinct from the Evo1, Evo2, Evo3 priority functions. The diagonals were left empty as we wanted to focus on cross-generalization. However, we are happy to complete the missing values in the camera-ready version.

W5

Thanks for flagging this. We will add multiple seed experiments to estimate variance in the camera-ready version. Note that the goal of this paper is to discover scale-invariant difficulty axes so the size of the graph (number of nodes is entity count) is controlled for.

Based on our analyses, the priority functions roughly weight some linear combination of the following properties of the story graph:

  • edge density (since the graph is multi-edge, each edge can have multiple labels)
  • entailed facts (unseen derivable edges from the graph. These are edges that could exist on the graph after some derivation steps and form the set of all possible query edges that we sample a query edge from)
  • derivation depth (multi-hop-ness required to go from a source node to tail node (including self-edges))
  • Diversity (number of unique relations etc.)

These are novel in the sense that they were not previously reported.

Thank you for your response, which addresses most of my concerns. I will therefore maintain my current score.

Reviewer_hBpHOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies automated generation of difficult relational-reasoning instances for neural models under Datalog rule bases. It uses LLM-guided evolutionary search, an agentic code-editing loop, and prompted LLM samplers to construct graph-generation strategies that challenge Edge Transformers, then trains a more robust model using the discovered data. Experiments on NoRA and an LLM-generated domain evaluate transfer, robustness, and whether difficulty is captured by depth, OPEC, and BL.

Critical strengths

The paper formulates benchmark generation as an adversarial sampling problem targeted at a reasoning model, rather than presupposing that a small set of manually selected structural metrics defines difficulty. Sections 3.1–3.3 provide three complementary implementations of this idea, and Tables 1 and 2 show that the discovered samplers substantially challenge models trained on other sampler distributions. This is consequential because it makes the paper’s central point concrete: robustness claims based on one handcrafted reasoning distribution can be brittle.

The empirical results go beyond a single sampler or model. Table 4 shows that instances found against an Edge Transformer also degrade EpiGNN, NBFNet, NCRL, and R-GCN, while Table 5 reports transfer of generic priority functions between NoRA and Iron Coast. Together with Figure 3, which shows that data augmentation improves robustness to further evolutionary search, this supports the practical relevance of automatically generated stress tests rather than merely demonstrating overfitting to one fixed ET.

Critical weaknesses

The evidence does not cleanly isolate the value of LLM-guided evolutionary search from the broader fact that adversarially selected graph distributions are difficult. Tables 1 and 2 compare several discovered samplers, but do not provide a matched non-LLM search baseline, such as random program search over the same priority-function language, hill-climbing/rejection sampling with the same evaluator budget, or a carefully tuned sampler optimizing the known metrics D, OPEC, and BL. The Claude-designed strategies are informative comparators, but they are themselves LLM-generated and are not controlled for search budget or access to rule-specific heuristics. This matters because the main methodological contribution is not merely that some manually or LLM-designed distributions are hard, but that FunSearch-style optimization and agentic search automate the discovery of previously unknown failure modes. A budget-matched comparison reporting mean and variance across search runs would resolve this without requiring a large new benchmark.

The claim that the discovered difficulty is “unexplained” by inference depth, OPEC, and BL is weaker than the paper sometimes suggests. Equation 2 and Table 3 assess how well an unspecified classifier predicts correctness from these three features, so high values establish that this particular predictive model extracts little information from those variables, not that the samplers have identified a qualitatively new, independent difficulty dimension. The paper does not specify in the main text the classifier family, feature transformations, training/test partitioning, or whether interaction and nonlinear effects were considered. This distinction matters because an inadequately specified predictor could leave substantial signal in D/OPEC/BL unmodeled. Reporting results for transparent linear and nonlinear classifiers, held-out evaluation, and feature ablations would make the interpretation substantially more convincing.

Questions for authors

In Section 4, the initial ET is trained using some examples from NoRA’s test-D, test-OPEC, and test-BL splits, while Table 3 evaluates models on test-D and test-OPEC. Were the examples used for initial-model training excluded from the instances evaluated in Table 3? If so, please state the exact disjoint partitioning procedure; if not, the comparative interpretation of these columns is compromised.

1 comment

Tables 1 and 2 compare several discovered samplers, but do not provide a matched non-LLM search baseline, such as random program search over the same priority-function language, hill-climbing/rejection sampling with the same evaluator budget, or a carefully tuned sampler optimizing the known metrics D, OPEC, and BL.

We are not aware of any existing LLM-free approaches which would be suitable as baselines for this experiment. Random program search would need to start from predefined primitive features, which we specifically wanted to avoid (i.e. we are interested in whether there are any aspects that make some problems challenging beyond what we already know). Similarly, we can indeed sample problems with high D, OPEC or BL values, but our purpose is to learn to sample problems that are difficult without having high values for these known metrics. To more clearly illustrate that our priority functions indeed find problems with relatively low D, OPEC and BL values, we have added a histogram of these values for several of the learned priority functions to the appendix (Figure 5). As the reviewer points out, our aim is to automate the discovery of previously unknown failure modes. We believe the experiments in the paper clearly demonstrate that this is now possible, with the help of LLMs. Whether similar (or better) results can be achieved without LLMs is an open question, but any efficiency gains would likely be limited, as a large part of the execution time comes from the need to re-train the edge transformer and the need for rescoring after each round, which together take up a similar amount of time as the components that are based on the LLM.

The claim that the discovered difficulty is “unexplained” by inference depth, OPEC, and BL is weaker than the paper sometimes suggests ... The paper does not specify in the main text the classifier family, feature transformations, training/test partitioning, or whether interaction and nonlinear effects were considered. This distinction matters because an inadequately specified predictor could leave substantial signal in D/OPEC/BL unmodeled. Reporting results for transparent linear and nonlinear classifiers, held-out evaluation, and feature ablations would make the interpretation substantially more convincing.

The details of the classifier are provided in Appendix 8.4. The classifier is a gradient-boosted tree, which is capable of picking up nonlinear effects and interactions between inference depth, OPEC and BL. For completeness, we have now also added a second result using a linear classifier: logistic regression with L1 regularisation. Similar results hold for L2 regularisation and for OLS. The direction of the results for the L1 linear model is similar to that of the gradient-boosted tree: the test-D and test-OPEC query sets continue to nearly always have less unexplained difficulty than the other query sets, across all trained ETs. The unexplained values across all entries go up when using the linear classifier. This is expected, as linear models are less powerful than nonlinear ones at distinguishing ET performance on a query from its difficulty metrics. The trends in Table 3 stay the same whether the unexplained values are computed on the queries used to fit the classifier or on held-out queries, for both the gradient-boosted and the linear classifiers.

In Section 4, the initial ET is trained using some examples from NoRA’s test-D, test-OPEC, and test-BL splits, while Table 3 evaluates models on test-D and test-OPEC. Were the examples used for initial-model training excluded from the instances evaluated in Table 3? If so, please state the exact disjoint partitioning procedure; if not, the comparative interpretation of these columns is compromised.

The initial ET was indeed trained on examples drawn from NoRA's test-D, test-OPEC and test-BL splits. However, the examples used for training and the examples evaluated in Table 3 are disjoint. Before the experiments, we randomly partitioned each of the three released NoRA 1.1 test splits into two equal, non-overlapping halves, where each instance is one query:

  • test-D: 6,944 instances, split into 3,472 for training and 3,472 held out.
  • test-OPEC: 29,498 instances, split into 14,749 for training and 14,749 held out.
  • test-BL: 2,598 instances, split into 1,299 for training and 1,299 held out.

Only a random subsample of the training half was used to train the initial ET. The test-D and test-OPEC columns of Table 3 are computed only on the held-out halves, so no instance evaluated in Table 3 was seen during training. We will add this partitioning procedure to Section 4 and the appendix, and release both partitions with the code.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.