Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement

Thank you so much for your insightful questions and constructive feedback!

Response to weakness

The results would be more informative if compared directly with human performance. Do any of these benchmarks contain human performance measures (e.g. I believe that there is already human behavioral data for miniSCAN in the original paper)?

Thanks for the suggestion! All of our experiments are largely motivated by cognitive scene literature. Therefore, they do have existing human performance as a reference. Note the exact setups, data, and evaluations in these studies might differ from ours. We include all existing human studies results in Appendix C.1 and refer it when discussing main results in Section 3.

The results on noisy rule induction are especially difficult to interpret without a human baseline. The authors cite a paper indicating that humans are somewhat robust to noise when inducing rules, but the amount of noise and the specific tasks will matter a lot.

We conducted human study using the same setup and added results in Appendix C.3. We observe that both the LM and humans perform worse on tasks with noisy examples. However, the relative performance drop of the LM is more significant. We clarified this in Section 4.2 footnote 9.

Throughout the paper, the authors appeal to intuition concerning putative human performance on the benchmarks they consider (e.g. in considering the potential for human reasoners to show a discrepancy between hypothesis generation and rule application), but intuition is not always a reliable guide regarding human performance. It would be good to qualify these statements a bit more (or, to the extent possible, to include a direct comparison with human performance).

Thanks for the feedback! We conducted more human studies to provide a more comprehensive head-to-head comparison between the LM and humans. The additional human experiments include asking crowdworkers to (1) write rules for 50 randomly sampled tasks from List Functions and MiniARC (as a comparison to Table 1), (2) write rules for perturbed tasks with a hint indicating that examples may be incorrect (comparable to the dashed line in Figure 4a), and (3) write rules for perturbed tasks without hints (comparable to the bar Figure 4a). We included all details of these human studies in Appendix C.3. While these studies do not cover all the experiments conducted with LMs due to cost constraints, we hope they provide a better understanding of the behaviors of LMs and humans and motivate future research in this area.

The 'task accuracy' measure seems designed to emphasize the consistency of the symbolic rule application. When looking at raw accuracy, the differences between symbolic and LLM rule application don't look nearly as large. I think this somewhat undermines the claim that their rule application abilities are so much worse than their hypothesis generation abilities.

We consider “task accuracy” as an alternative metric as it captures a desirable property of an induction system: it should ideally consistently solve examples within a task. We use this metric to approximate the model’s true understanding of a task because a model is less likely to solve all examples without using the expected computation. Although the differences in raw accuracy are not as large as those in task accuracy, they are still significant for certain tasks (e.g. relative performance drop is around 27% for MiniSCAN and around 42% for MiniARC). In addition, we observe that more advanced prompting techniques, such as self-consistency prompting and zero-shot CoT prompting, also do not bridge the gap (see Appendix B.2 for new experiments). As we argue in Section 4.1, we do not claim that we should expect LMs to behave as effectively as symbolic interpreters, but often the gaps are still large enough to support the argument.

Thank you for your valuable feedback and insightful suggestions! We appreciate that you found our paper interesting and insightful.

An analysis of the complexity of the rules used to generate the data would be interesting. Comparing the complexity of the hypothesis across tasks and domains might give some insight into the model performance.

It’s definitely very interesting to analyze the relationship between the complexity of the rules and model performance. However, it is challenging to determine a good measure of complexity. As a preliminary experiment, we investigate how rule complexity affects model performance using List Functions, as its data was generated by programs. For each task, we collect its Python Lambda expression and analyze its complexity using abstract syntax tree (AST), similar to Bi et al. (2023). Note that the original List Function dataset uses a domain-specific language (DSL). This DSL defines symbols for basic list operations following a Lisp-like syntax. For instance, a list [1, 2, 3] is represented as (cons 1 (cons 2 (singleton 3))). We did not consider this DSL for our analysis, as we hypothesize that Python is better represented in LMs' pre-training data than this DSL. Analyzing Python expressions, therefore, could provide a better estimate of rule complexity.

We consider both primitive and structural complexities and investigate their correlations with model performance. The former indicates the learnability of individual primitive operations, while the latter reflects the difficulty of the compositional structures of the rule, which we approximate using the number of nodes and tree depth of the AST.

We first examine how different primitive operations contribute to rule induction. We train a logistic regression model to predict LM's task accuracy on a new instance, using the counts of different types of nodes as features. The logistic regression models achieve an averaged test accuracy of 68.4% with a small number of features, suggesting that the model performance is somewhat predictable based on the primitives of the rule. We use the coefficient as an approximation of the learnability of the primitive operations. These coefficients vary across different primitives, with some operations such as In being easier to learn than others like Sub.

For structure complexity, we measure the Spearman correlations between test accuracy and the structure complexity measurements. The number of nodes has a correlation of -0.31, and tree depth has a correlation of -0.37. Tasks with high accuracy generally have a relatively small number of nodes and tree depth. However, some programs with low structural complexity also have low accuracy, indicating that other factors, such as the aforementioned primitive complexity, should also be considered.

Zhen Bi, Ningyu Zhang, Yinuo Jiang, Shumin Deng, Guozhou Zheng, Huajun Chen. When Do Program-of-Thoughts Work for Reasoning?

Similarly, the complexity of the human induced and LLM induced rules might be interesting to analyze.

Since the human-induced and LM-induced rules are often in free-form natural language, it is even more challenging to measure their complexity. Measures such as minimum description length and the number of unique n-grams could be potential solutions. However, it is unclear whether these measures correlate with the complexity of rules in our setup. We agree that this is a very interesting direction, but it is beyond the scope of this paper. Therefore, we leave this as a direction for future work.

Thank you for your valuable feedback! We appreciate your support for our paper.

Response to weakness

A few of the experiment setups feel a bit contrived - for example, randomly perturbing a set of items in a small set of experiments, of course, makes the task harder for a language model since it also requires it to infer that the noise is noise and not itself a deterministic part of the rule.

To better calibrate model performance, we conducted human study using the same setup and added results in Appendix C.3. We observe that both the LM and humans perform worse on tasks with noisy examples. However, the relative performance drop of the LM is more significant. We clarified this in Section 4.2 footnote 9.

The section on familiarity of exemplars should also likely mention Dasgupta et al.'s "Language models show human-like content effects" there.

Thanks for the pointer! We discussed this paper in Section 4.2 footnote 10.

Response to questions

In practice, did you see this when refining hypotheses? It would be interesting to see how the number of revisions affects performance, similar to Table 2 in the concurrent "Hypothesis Search" paper from Wang et al. I see there is some version of this in this paper's Table 2, but given the emphasis that this paper places of hypothesis refinement, I'd expect a bit more detail. Especially given the self-consistency, it would be valuable to understand the tradeoff between more attempts and more revisions.

Huang et al. (2023) evaluates intrinsic self-correction without external feedback, which is similar to Self-Refine. As shown in Table 1, we similarly found an iterative approach without external feedback is insufficient. However, we did observe performance improvement over iterations for all datasets when coupled with external interpreters. The results are shown below. See Figure 5 in Appendix B.3 for a better visualization. This is consistent with the findings in Huang et al. (2023), as they discussed in Section 5 “Leveraging external feedback for correction”.

Raw Accuracy

Task Accuracy

However, as we mentioned at the end of Section 4.3, qualitatively, in some cases, LMs tend to make minor modifications rather than starting from entirely new hypotheses. Therefore, in cases where the initial hypothesis is completely off, iterative refinement tends to be less effective.

We agree that it is certainly interesting to investigate the tradeoff between the number of hypotheses (N) and the maximum number of iterations (T). We did preliminary exploration (in Table 1) to demonstrate the correlations between model performance and these two hyperparameters. For tasks where LMs achieve strong performance, such as ACRE and MiniSCAN, a limited number of iterations is already effective. For tasks like MiniARC, where LMs perform poorly, the trends remain positive after the maximum number of iterations.

Note that the maximum number of iterations is bounded by the context lengths of LMs. Empirically, we find it is infeasible to further increase T. An alternative could be tracking only the latest K iterations. Additionally, increasing N leads to more API calls, which can be computationally expensive. A summarization strategy, as suggested in Wang et al. (2023) might offer a solution. Therefore, identifying the best tradeoff between more attempts and more revisions could require more method-wise exploration, which is beyond the scope of this paper. We hope our experiments motivate future work along this direction.

Thank you for your valuable feedback! We appreciate that you found our approach effective and our experiments comprehensive.

Response to weakness

For the example perturbation experiment in section 4.2, there are no studies on how well humans can actually perform on perturbed tasks. It is hard to judge how big the performance drop of LMs is compared with humans.

Thanks for the feedback! We conducted human study using the same setup and added results in Appendix C.3. We observe that both the LM and humans perform worse on tasks with noisy examples. However, the relative performance drop of the LM is more significant. We have clarified this in Section 4.2 footnote 9.

Experiments in 4.1 and 4.2 are conducted with simple prompting which may not be the most effective method to elicit this type of reasoning from the model.

For section 4.1, we consider two alternative prompting techniques for rule application: self-consistency prompting (SC) and zero-shot chain-of-thought (0-CoT). The results are shown below. We do not observe significant performance differences across these methods, except on ACRE, where 0-CoT underperforms other methods in task accuracy. We included detailed results and discussions in Appendix B.2 and clarified this in Section 4.1 Our results show the rule application performance is consistent across various prompting methods. It would be interesting to explore more advanced prompting techniques for our setting, but that is out of scope of this paper.

Raw Accuracy

Task Accuracy

For section 4.2, all perturbation experiments use iterative hypothesis refinement (T=3, N=5), which has the strongest performance in our main experiments. We clarified this in the main text and included results using other models and configurations in Appendix B.2.

The generalizability of the findings in 4.3 is doubtful because only one type of prompt is used to generate rules from LM. According to the appendix, example rules on List Fn and MiniARC are generated from LM with a prompt that contains no format instruction. It is unknown whether LMs can generate human-like inductions with more guidance or provided with human-induced rules as few-shot examples.

We did not introduce task-specific format instructions for List Functions and MiniARC, as they cover a wide range of concepts, making it challenging to determine the most optimal constraints. To investigate whether other prompts would lead to different behaviors, we evaluate an alternative hypothesis generation prompt that includes task-specific heuristics (see Appendix B.2, Task-specific Heuristics). Specifically, we use MiniARC and add a detailed task description in the prompt (Table 10). This does help LMs to generate more human-readable rules (Table 11) for a fraction of examples, but these rules are still generally distinguishable from those induced by humans. Additionally, we did not observe performance improvement by imposing these constraints. It is certainly possible that other guidance or few-shot examples could encourage LMs to generate human-like rules. However, the former requires more prompt engineering, and the latter requires additional human annotations, which are beyond the scope of this paper. We mention these alternatives as potential directions for future work.