PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models can Learn Rules

Zhaocheng Zhu, Yuan Xue, Xinyun Chen, Denny Zhou, Jian Tang, Dale Schuurmans, Hanjun Dai

arXiv:2310.07064v3cs.AIcs.CL

TL;DR

LLMs can generate incorrect rules when reasoning depends on implicit knowledge, motivating a way to discover domain-specific rules from standard datasets without rule annotations. HtT induces and verifies rules on training examples, filters them into a library, and prompts the model to retrieve and apply those rules to test questions. Across GPT-3.5 and GPT-4 on relational reasoning, numerical reasoning, and concept learning, HtT improves baseline prompting by an absolute 10–30% in accuracy in most cases.

  • Problem

    LLMs can generate incorrect rules when reasoning depends on implicit knowledge, motivating a way to discover domain-specific rules from standard datasets without rule annotations.

    Source: §1 · p. 2, §3 · p. 3

  • Method

    HtT induces and verifies rules on training examples, filters them into a library, and prompts the model to retrieve and apply those rules to test questions.

    Source: §1 · p. 2, §3 · p. 3, §3.2 · p. 4

  • Results

    Across GPT-3.5 and GPT-4 on relational reasoning, numerical reasoning, and concept learning, HtT improves baseline prompting by an absolute 10–30% in accuracy in most cases.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The learned rules can transfer to the textual version of CLUTRR, and the conclusion presents HtT as a direction for learning textual knowledge with LLMs.

    Source: §1 · p. 2, §6 · p. 10

    HtT’s scope resembles its base few-shot method and is limited to tasks whose needed rule library is moderately small (≤500 rules in our experiments).

    Source: §3.3 · p. 4

Abstract

from arXiv · show

When prompted with a few examples and intermediate steps, large language models (LLMs) have demonstrated impressive performance in various reasoning tasks. However, prompting methods that rely on implicit knowledge in an LLM often generate incorrect answers when the implicit knowledge is wrong or inconsistent with the task. To tackle this problem, we present Hypotheses-to-Theories (HtT), a framework that learns a rule library for reasoning with LLMs. HtT contains two stages, an induction stage and a deduction stage. In the induction stage, an LLM is first asked to generate and verify rules over a set of training examples. Rules that appear and lead to correct answers sufficiently often are collected to form a rule library. In the deduction stage, the LLM is then prompted to employ the learned rule library to perform reasoning to answer test questions. Experiments on relational reasoning, numerical reasoning and concept learning problems show that HtT improves existing prompting methods, with an absolute gain of 10-30% in accuracy. The learned rules are also transferable to different models and to different forms of the same problem.

1 Introduction

LLMs can reason step by step, but they may lack or misapply domain-specific rules. HtT learns a rule library from training examples and applies it to new questions, improving prompting results across several reasoning tasks.

1 Introduction

  • Domain-specific rules are needed for correct reasoning, yet LLMs can generate incorrect rules, especially on tasks that depart from conventional knowledge.The paper seeks automatic rule discovery from standard datasets, without rule annotations.Source: §1 · p. 2
  • HtT learns textual rules from examples, filters them into a library, then prompts the model to use that library on new samples.Induction generates and verifies rules; deduction applies the learned rules. The stages can use prompts derived from existing few-shot methods.Source: §1 · p. 2
  • Across GPT-3.5 and GPT-4 and three datasets, HtT improves baseline prompting by an absolute 10–30% in accuracy in most cases.The datasets cover relational reasoning, numerical reasoning, and concept learning.Source: §1 · p. 2
  • The learned rules can transfer to the textual version of CLUTRR, and ablations attribute most performance gains to fewer incorrect rules.The paper also reports a log-linear trend between accuracy and the number of training examples on all three datasets.Source: §1 · p. 2

2 Preliminaries

The preliminaries frame reasoning as deriving facts using rules, and distinguish deductive application from inductive rule discovery. They also situate LLM prompting among approaches that rely on implicit or explicit rules.

2 Preliminaries

  • In this paper, rules are reusable intermediate steps across samples, rather than rules in the formal-logic sense.The preliminaries distinguish facts as information describing a current state and rules as functions transforming facts under conditions.Source: §2 · p. 2
  • Deductive reasoning derives new facts from known facts and rules; matching rules against facts is unification, and step ordering may require planning.Forward and backward chaining are given as examples of planning algorithms.Source: §2 · p. 3
  • Chain-of-thought and least-to-most prompting rely on implicit rules, whereas Selection-Inference and LAMBADA operate on given facts and rules.The paper characterizes the latter methods as searching for an optimal deduction order.Source: §2 · p. 3
  • Inductive reasoning derives general rules from observed facts, and useful rules should combine broad example coverage with correct predictions.Rules overly specific to observed facts may not generalize to future predictions.Source: §2 · p. 3

3 Hypotheses-to-Theories: Learning a Rule Library for Reasoning

HtT addresses errors from implicit rules by learning an explicit rule library from training examples and retrieving its rules during test-time reasoning. Its scope depends on both the size of the needed library and the base prompting method’s ability to induce rules.

3 Hypotheses-to-Theories: Learning a Rule Library for Reasoning

  • HtT learns textual rules from training examples through induction, then prompts the model to retrieve and apply the resulting library to test questions.The two stages use few-shot prompting and parallel the training and test stages of neural networks, while learning textual rules instead of model parameters.Source: §3 · p. 3, §3.2 · p. 4

3.1 Induction Stage: Learning A Rule Library By Generation and Verification

  • Rules are generated for question-answer examples and verified against ground-truth answers; the library retains rules meeting minimum coverage and confidence thresholds.Coverage counts rule occurrences, while confidence is the average accuracy of examples where a rule occurs.Source: §3.1 · pp. 3–4
  • Induction from deduction declares a rule at each deduction step, letting both stages share a base prompt such as chain-of-thought or least-to-most.This adapts a deductive prompt to rule generation and verification, reducing prompt-engineering effort and allowing comparison with the base method.Source: §3.1 · p. 4

3.2 Deduction Stage: Explicit Reasoning with the Rule Library

  • To aid retrieval from a large, unstructured library without an external retriever, HtT organizes rules hierarchically and uses XML tags to specify clusters.The library is prepended to a deductive prompt, whose exemplars teach retrieval when a rule is needed.Source: §3.2 · p. 4

3.3 Discussion: Why Does HtT Work? What Kind of Tasks Can It Solve?

  • HtT is expected to work when training examples yield most necessary rules and retrieving those rules is easier than generating them correctly.The task should need a moderately small library (≤500 rules in the experiments), and the base few-shot method should perform reasonably on training examples (≥20% accuracy in the experiments); planning tasks are cited as an excluded case.Source: §3.3 · pp. 4–5

4 Experimental Evaluation

The evaluation tests HtT as an augmentation to few-shot prompting across relational, numerical, and concept-learning tasks, alongside ablations. Results report gains over prompting baselines and examine rule quality, transfer, and data needs.

4.1 Implementation Details

  • Evaluations use GPT-3.5 and GPT-4, with Gemini Pro also tested; LtM costs 3–5× as much as CoT, so rule induction and hyperparameter selection use CoT.The authors note this may slightly underestimate HtT performance with LtM.Source: §4.1 · p. 5

4 Experimental Evaluation

  • Across relational, numerical, and concept-learning tasks, HtT improves prompting baselines in the evaluated settings.The task-specific results and qualifications are described below.Source: §4.2 · p. 5, §4.3 · p. 6, §4.4 · p. 7

4.2 Relational Reasoning

  • HtT improves CoT and LtM on CLUTRR by 11.1–16.4% in average accuracy across both models.With GPT-4-induced rules, GPT-3.5 CoT performance increases 27.2%; symbolic-version rules also improve GPT-4 on textual CLUTRR.Source: §4.2 · p. 5, Table 1 · p. 6

4.3 Numerical Reasoning

  • On Arithmetic, HtT consistently improves CoT and LtM, while 0-shot CoT performs worst across both models and all base systems.The authors attribute 0-shot CoT errors to converting non-decimal inputs to decimal, calculating, then converting back.Source: §4.3 · p. 6, Table 2 · p. 6

4.4 Concept Learning

  • HtT boosts 4-shot CoT on List Functions by 18.5–18.7% in raw accuracy and 10.2–14.5% in task accuracy across both models.With GPT-4-induced rules, GPT-3.5 task accuracy reaches 34.4%, doubling its 4-shot CoT performance; GPT-4 is more robust across difficulty levels.Source: §4.4 · p. 7, Table 3 · p. 7

4.5 Ablation Studies

  • Manual analysis of 100 CLUTRR and base-16 Arithmetic examples attributes most HtT performance gain to fewer incorrect rules.Predictions were categorized as correct, incorrect rules, or other.Source: §4.5 · p. 7, Figure 2 · p. 8
  • Replacing learned rule conclusions with random answers significantly hurts performance, indicating that learned rules are necessary for HtT.The authors conjecture that differences from prior findings reflect their focus on multi-step reasoning rather than simple classification.Source: §4.5 · p. 7, Table 6 · p. 8
  • Performance follows a log-linear trend with induction examples; significant gains require 500 examples for CLUTRR and base-11, versus 100 for base-16 and base-9.One sample per task yields some gain on List Functions; HtT discovers more than 85% of rules in all reported datasets.Source: §4.5 · p. 8

5 Related Work

The section places HtT among reasoning-prompting, program-synthesis, and rule-learning approaches, emphasizing its use of learned natural-language rules for deduction.

5 Related Work

  • Earlier natural-language reasoning work progressed from memory-based models (Kumar et al., 2016) to transformer and pretrained-language-model approaches.The section cites work on deductive reasoning, implicit knowledge, and program execution (Clark et al., 2020; Talmor et al., 2020; Nye et al., 2021).Source: §5 · p. 8
  • Chain-of-thought (Wei et al., 2022c), least-to-most (Zhou et al., 2023), and decomposed prompting (Khot et al., 2023) rely on knowledge stored in LLM parameters rather than extracting rules explicitly.Other approaches provide facts and rules as input and search for proof traces (Creswell et al., 2023; Kazemi et al., 2023).Source: §5 · p. 8
  • HtT is presented as the first method to induce rules from examples and apply them deductively to solve reasoning problems.Earlier prompting approaches rely on implicit model knowledge, while methods that take explicit rules as input search for proof traces.Source: §5 · pp. 8–9
  • Unlike LLM-oriented library-learning work (Cai et al., 2023), HtT learns natural-language rules without requiring a symbolic program executor.The section describes HtT as sharing library learning’s goal of reusable functions that generalize to new examples.Source: §5 · p. 9
  • Classical rule-mining methods filter by support and confidence, while HtT uses rule frequency and accuracy through LLM prompting.Other rule-learning methods often rely on predefined templates or dedicated solvers; HtT is applicable to generative LLMs.Source: §5 · p. 9

6 Discussion and Conclusion

The discussion concludes that HtT boosts prompting baselines across three reasoning areas, while noting model-knowledge, context-length, ethical, and reproducibility boundaries.

6 Discussion and Conclusion

  • HtT’s rule library is limited by the LLM’s context length, and scaling deduction when the library cannot fit remains an open problem.The method also requires a base model with reasonably strong knowledge and retrieval ability, particularly for non-decimal systems.Source: §6 · pp. 9–10
  • The paper concludes that HtT significantly boosts baseline prompting on relational reasoning, numerical reasoning, and concept learning.It presents learning textual knowledge with LLMs as a new research direction.Source: §6 · p. 10

Ethics Statement

  • HtT may augment malicious uses, and LLM-generated knowledge may carry existing biases involving gender, race, or religion.The paper points to better alignment with human values and bias reduction as future work.Source: Ethics Statement · p. 10

Reproducibility Statement

  • Exact results may not be reproducible with future GPT-3.5 and GPT-4 versions because those models are frequently updated.The authors expect the performance gain over base prompting methods to remain observable.Source: Reproducibility Statement · p. 10

A Implementation Details

The implementation uses fixed few-shot exemplars, string-template rule extraction and filtering, a specified answer-matching procedure, and XML tags to organize rule retrieval.

A Implementation Details

  • Few-shot baselines use the first five non-trivial CLUTRR and Arithmetic examples and one example from each of four P1 List Functions groups.The same exemplars are used across few-shot methods; least-to-most offloads rule generation and retrieval to a separate prompt.Source: A Implementation Details · p. 15
  • Answers are evaluated by checking whether the ground-truth answer appears as a full word in the prediction’s last sentence; multiple answers count as wrong.Partial word matches are excluded.Source: A Implementation Details · p. 15
  • Rule extraction uses regular-expression string templates, and the library filters rules by minimum coverage and confidence; Table 7 lists dataset-specific best configurations.The authors state that templates need not be engineered, since incorrectly recalled rules can be filtered.Source: A Implementation Details · p. 15, Table 7 · p. 15
  • XML tags organize rules into a hierarchy, breaking a difficult retrieval problem into easier steps and significantly boosting HtT on CLUTRR and Arithmetic.The LLM generates tags at each level before outputting the retrieved rule.Source: Figure 5 · p. 15, A Implementation Details · p. 16

B Prompts

This appendix specifies and illustrates prompts for CLUTRR, arithmetic, and list-function tasks, covering CoT, HtT, and LtM variants and the use of learned rules during reasoning.

B Prompts

  • All HtT rule libraries contain rules generated during induction; prompt examples demonstrate formatting and do not supply human-annotated rules.HtT prompts ask the model to use provided knowledge where possible, with rules presented using XML tags.Source: B Prompts · p. 16
  • For symbolic CLUTRR, Prompts 1–5 cover zero-shot CoT, five-shot CoT, CoT+HtT, LtM, and LtM+HtT reasoning variants.HtT variants provide tagged rules; LtM variants query the model about a relation pair whenever reasoning encounters a rule.Source: §B.1 · pp. 16–18
  • For textual CLUTRR, Prompt 6 uses five-shot CoT to extract triplets, find a relation path, and reduce its relations; Prompt 7 adds learned HtT rules.The HtT example retrieves tagged rules to reduce successive relation pairs on the path.Source: §B.1 · pp. 19–20
  • Prompts 8–12 present different prompting methods for the base-16 dataset; for base-11 and base-9, the same prompts are used, with exemplars changed in corresponding few-shot prompts.Source: §B.2 · p. 21
  • The 5-shot arithmetic CoT+HtT prompt supplies learned rules as knowledge and demonstrates base-16 addition step by step, tracking carries to produce the answer.The example adds EC and DD to obtain 1C9, using carry-tagged rule applications.Source: §B.2 · p. 22
  • For arithmetic, LtM calls a separate prompt when it encounters a rule, while LtM+HtT adds provided knowledge and retrieves tagged rules for those calls.Examples show retrieval of carry and no-carry rules for base-16 digit sums.Source: §B.2 · pp. 23–24
  • List Functions prompts also include 0-shot CoT and 4-shot CoT formats that ask the model to infer the function from examples and apply it to test queries.The CoT+HtT variant is presented as a 4-shot prompt.Source: §B.3 · pp. 24, 26
  • For List Functions, the CoT+HtT prompt presents examples, test questions, candidate functions with confidence scores, and answers using the inferred rule.The illustrated rule appends 3 if a list contains 3, otherwise appends 9 if it contains 9, and otherwise leaves the list unchanged.Source: §B.3 · pp. 26–27

C Rule Libraries Learned by HtT

The section presents rule libraries learned across arithmetic, relational reasoning, and list-function tasks, ranging from close matches to ground truth to ambiguous or weakly supported rules.

C Rule Libraries Learned by HtT

  • The 98-rule CLUTRR library includes kinship compositions such as daughter’s uncle becoming brother and brother’s son becoming nephew.Source: §C.1 · p. 29
  • 98.5% precision and 92.2% recall for 413 GPT-4 rules on base-16; base-11’s 220 rules reached 90.5% precision and 99.5% recall, while base-9’s 124 reached 99.2% and 85.5%.The paper computes precision and recall by comparing learned rules with rules induced by an oracle model on training examples.Source: §C.2 · pp. 29–31
  • P1 libraries capture operations such as selecting the third element, swapping the first and fourth, and adding 9 at the start and 7 at the end.Source: §C.3 · pp. 31–32
  • List-function libraries also recover longer transformations, including repeating the first element ten times and concatenating fixed sequences around the input.Source: §C.3 · pp. 33–34
  • For difficult P3 tasks, learned rules for keeping elements with even tens digits diverge from ground truth, and another task has no rule above 0.1 confidence.Source: §C.3 · p. 34
  • Other learned list operations include repeating each element according to its tens digit and summing even elements.Source: §C.3 · p. 35

D Full Experimental Results

Across the full results, HtT reduces errors attributed to incorrect rules, while retrieval remains a distinct source of errors. XML tagging improves HtT performance, and the appendix reports results on textual CLUTRR using rules learned on symbolic CLUTRR.

D Full Experimental Results

  • The error analysis distinguishes correct predictions, errors involving incorrect rules, and other errors, with incorrect-rule and retrieval errors further categorized.The five categories are correct, incorrect rules only, incorrect rules plus other causes, retrieval, and non-retrieval.Source: D Full Experimental Results · p. 35
  • Table 8 reports results on textual CLUTRR using rules learned on symbolic CLUTRR.Source: Table 8 · p. 35
  • XML tagging significantly boosts HtT, suggesting retrieval matters even when good rules are available.The ablations consider different hierarchy levels as well as unsorted rules without hierarchy.Source: D Full Experimental Results · p. 35, Table 9 · p. 36, Table 10 · p. 36
  • HtT significantly reduces errors attributed to incorrect rules; on CLUTRR, some errors still arise because required rules are missing or not retrieved.The authors suggest a more complete rule library and retrieval fine-tuning as possible mitigations.Source: D Full Experimental Results · p. 35, Table 11 · p. 36

E Experimental Results of Gemini Pro

With Gemini Pro, HtT improves prompting results across CLUTRR, Arithmetic, and List Functions. On CLUTRR, its average-accuracy gains over CoT and LtM are 10.2–19.2%.

E Experimental Results of Gemini Pro

F Examples of Model Outputs

The examples contrast CoT and CoT+HtT outputs on relational reasoning, base-16 addition, and List Functions. They illustrate how the inferred or retrieved rules can change intermediate steps and final answers.

F Examples of Model Outputs

  • On the Sarah–Christine relation example, CoT concludes “sister,” whereas CoT+HtT concludes “granddaughter.”HtT retrieves relation-composition rules at each step, while the CoT example selects a relation for “grandson’s uncle.”Source: §F.1 · pp. 37–38
  • For the base-16 question asking for F55 + 85E, two cited worked answers report 1E19 and 17B3, respectively, and each passage displays its carry-step calculation.Source: §F.2 · p. 38
  • For 47D2 + D292 in base 16, CoT answers 11AC4 and CoT+HtT answers 11A64.Source: §F.2 · p. 39
  • In one List Functions example, CoT infers multiples of the last element, while HtT infers multiples of the smallest element.For input [7, 44, 98], the respective outputs are [98, 196, 294] and [7, 14, 21].Source: §F.3 · pp. 39–40
  • Another List Functions example infers a transformation that keeps the first and last numbers and sums the middle numbers.For [55, 7, 24, 6, 1, 0, 3, 4], the shown output is [55, 41, 4].Source: §F.3 · p. 41
Loading 2310.07064v3…