Reasoning in human and machine intelligence

Noah D. Goodman

Stanford University�July 13, 2023

ACL NLRSE Workshop

The space of intelligences

The space of flying things

The space of flying things

Contingent facts

Universal principles

Functional demands

Airfoil, Bernoulli

Takeoff speed

Made from keratin

Reasoning

What is reasoning? �Where does reasoning come from?�Are LLMs able to reason? �What are the principles vs contingent facts of human/machine reasoning?

Is Socrates mortal?

Socrates is a man.

Men are mortal.

Yes, Socrates is mortal.

3x-1=2. What is x?

(3x-1)+1=2+1

3x=3

3x/3=3/3

x=1

Chain of Thought (CoT) in LLMs

Chain of Thought (CoT) in LLMs

Chain of Thought (CoT) in LLMs

Chain of Thought (CoT) in LLMs

Old days -- Human-sourced Rationales (2019)

Is this system 2?

Why is Chain of Thought useful for LLMs?

​

Is there a universal principle that can also help explain the origins of human reasoning?

A simple model to explore CoT / reasoning

Assume the world is a joint distribution defined by a Bayes net.

The “brain” sees samples and learns a density over sequences of variables, q(“A=1,C=0,B=1”).

Estimate conditional distribution:

Directly: p(C=c|A=a) ~ q(c|“A=a,C=”)

By sampling intermediate variables (a Monte Carlo estimate):� p(C=c|A=a) ~ q(c|”A=a,B=b,C=”) where “B=b,C=” ~ q

The value of reasoning is measured as the gap between direct and free-generation (i.e. Monte Carlo) estimators.

Prystawski, Li, Goodman (arxiv, 2023)

Training sequence density estimator (transformer)

Observation distribution samples subset of variables for each training sequence.��Compare local (Cf ego-centric) to global observation conditions.

Inference accuracy evaluation

Results (summary)

When training data is organized into local observations (but not global or random) reasoning through intermediate variables (“Chain of Thought”) is more accurate.

Theorem: For chain bayesnet and observations consisting of adjacent pairs of variables. A risk-minimizing sequence estimate q. The direct estimator has higher bias than the “Chain of Thought” estimator.

Data complexity is also vastly lower when using local observations.

So, reasoning (viz a vis CoT for sequence models) is useful when training data are organized locally.

Education and practice lead to better reasoning for people.

​

Can LLMs improve from practice? From feedback?

Self-Taught Reasoner (STaR) - Basic version

Question

Question, Rationale, Answer

Rationale, Answer

Finetune

Correct Answer

Rationale Generation

LLM

STaR (Basic) - Results

​

• Base model: GPT-J (6B) for reference GPT-3 (175B)
• Three datasets
• Arithmetic (taken from the scratchpad paper).
• Commonsense reasoning QA.
• Multiple choice
• Math word problems

Arithmetic with STaR (Basic)

Using STaR to finetune GPT-J (6B)

# digits:

CommonsenseQA with STaR (Basic)

68.8% dev acc w/ only 69.7% of training data! (at most ~78% train)

175B params

($$$)

6B params

6B params

6B params

STaR Basic version - Hitting a Ceiling

• However, model only ever learns to solve a subset of the examples - eventually its learning fails to generalize

STaR Basic version - Hitting a Ceiling

• However, model only ever learns to solve a subset of the examples - eventually its learning fails to generalize
• Why?

STaR Basic version - Hitting a Ceiling

• However, model only ever learns to solve a subset of the examples - eventually its learning fails to generalize
• Why?
• No signal from the wrong answers
• Is only seeing a subset of the training data
• Saturating on the correct answers (as it’s generated by the model)

STaR - Rationalization

Question

Question, Rationale, Answer

Rationale, Answer

Finetune

?

LLM

Rationale Generation

STaR - Rationalization

Question

Question, Rationale, Answer

Rationale, Answer

Finetune

Hint

LLM

Q: Where do you put your grapes just before checking out?

Answer Choices:

(a) mouth

(b) grocery cart (Correct)

(c) super market

(d) fruit basket

(e) fruit market

Rationale Generation

STaR - Rationalization

Question

Question, Rationale, Answer

Rationale, Answer

Finetune

Hint

Rationale, Answer

Rationalize

Rationale Generation

LLM

STaR - Rationalization

Question

Question, Rationale, Answer

Rationale, Answer

Finetune

Hint

Rationale, Answer

Rationalize

LLM

Rationale Generation

STaR - Rationalization

Reasoning: Question → Rationale, Answer

Rationalization: Question, Answer → Rationale

How can we learn from the wrong examples? Rationalization

• When it gets wrong
• Ask it to justify the right answer
• Add to fine-tuning dataset as if solved without hint

STaR - Examples

STaR - Results (Commonsense QA)

Interlude – human like?

Human reasoning shows strong content effects – we are much more likely to endorse conclusions consistent with commonsense knowledge.

E.g. Evans, Barstan, Pollard (1983)

Human reasoning benefits from externalized / formalized systems.

​

For example, we can use logic to avoid content biases and other fallacies.

​

Can LLM reasoning benefit from external reasoning tools?

Peano theorem proving language

Dependently-typed language: propositions as types, proofs as program

nat : type.

z : nat.

succ : [nat -> nat].

one : nat = (succ z).

leq : [nat -> nat -> prop].

z_leq_n : [(’n : nat) -> (leq z ’n)].

n_leq_sn : [(’n : nat) -> (leq ’n (s ’n))].

Similar to:

Peano: finite action space

• In other theorem-proving languages, each line can create arbitrary new objects as long as they type-check
• E.g., let n = (s (s (s (s (s … z)))))).
• In Peano, we only allow constructions from one axiom and existing objects
• Arbitrary objects can still be constructed, in multiple steps
• We use the type system to enumerate valid constructions given an axiom
• Since axioms are finite and set of existing objects is also finite, the action space is finite.

Peano: minimal yet expressive

Algebra

�Solve y = x², � x + 3 = 10,�

Peano: minimal yet expressive

41

Geometry

�Given an isosceles �triangle where the �unequal angle is 100^o,�find the other �two angles.

…

Peano: minimal yet expressive

42

Number Theory

�[CS 103 problem]

If n is even, prove�that n² is also even.

Using Peano for constrained generation in LLMs

Guide tools, LogicGuide

We first introduce a new type of LM tool, guides:

• When LM generates [[ it switches to constrained generation, forced to yield tokens that are valid continuations according to an external computation.
• When LM closes with ]] it goes back to free generation.

LogicGuide uses Peano to compute logically valid steps:

• Formalization steps introduce new objects, relations, or axioms.
• Inference steps are constrained to follow from existing terms by one step of formal reasoning.

Example

Few-shot demonstration, that shows model how to use the reasoning tool. Then:

Syllogism task

Multi-step logical reasoning

STaR bootstrapping

Naive STaR does not make progress on these problems because there is a high chance of being right by chance (STaR reinforces these hallucinations).

STaR restricted to update only with valid guide arguments (which could be wrong due to formalization failures) makes rapid progress.

Reasoning across the space of intelligences

Contingent facts

Universal principles

Functional demands

Airfoil, Bernoulli

Takeoff speed

Made from keratin

Contingent facts

Universal principles

Functional demands

Sequence prediction. �Local data observation. �Freely generated intermediate states.

Self-improvement. Revision.

Cultural transmission.

Externalization.

LLMs speak all their thoughts.

Humans have small working memory.

Does this kind of learning to reason work in more difficult domains?

​

How about education-relevant math?

Case study: Khan Academy algebra

The Search for Solutions

​

• Any theorem-proving language (e.g. Lean, Coq, Isabelle) can represent the axioms and problems we're analyzing. (So can free text – e.g. LaTeX.)�
• But searching for solutions in them is hard: �infinite action space at any state�
• How to do search?
• Learn to generate actions: need pre-training data
• Or, make action space finite…

57

Formalizing Khan Academy in Peano

58

Axioms: directly written in Peano

�States: set of objects constructed so far

�Actions: all ways to apply axioms on existing objects�

Problems: we turn exercises from Khan Academy into templates (e.g., x + 7 = 9 → x + c1 = c2)��Goals: simple solution checker for each section

Formalizing Khan Academy in Peano

59

Well-defined�search problem.

Solving problems through search

Combinatorial search space even in simple domains:�need heuristics to guide search

Can we learn search heuristics?

60

How to guide search?

• Could hand-engineer heuristics. But:
• Effort needs to be repeated for each domain
• Even then, might be incomplete!�
• Instead, we can learn search heuristics

61

Learning to solve problems�Contrastive Reinforcement Learning of Symbolic Reasoning Domains

Gabriel Poesia, WenXin Dong, Noah D. Goodman, NeurIPS 2021

62

Learning to solve problems

​

• Main idea: "Expert Iteration"*
• Use a policy-guided search algorithm (e.g., beam search)
• With a random policy, some problems can be still solved
• Imitate successful solutions to improve the policy
• Iterate�
• Contrastive Policy Learning handles variable action space:
• States and actions treated as strings
• Policy learning is reduced to representation learning

63

Contrastive Reinforcement Learning of Symbolic Reasoning Domains

Gabriel Poesia, WenXin Dong, Noah D. Goodman, NeurIPS 2021

​

*Cf. Anthony, Thomas, Zheng Tian, and David Barber. "Thinking fast and slow with deep learning and tree search." Advances in Neural Information Processing Systems 30 (2017).

Solve a batch of random problems (using beam search with the current policy)

Train the policy to imitate successful trajectories

Contrastive Policy Learning (ConPoLe)

​

64

Contrastive Policy Learning (ConPoLe)

​

65

I.e. Bring correct next states closer, send failing next states further..

ConPoLe on Khan Academy in Peano

​

66

ConPole learns to solve all problems in the first two sections.���However, it gets stuck on the next three…

Why?

• As we move from section to section, solutions get longer and longer in terms of the starting axioms
• Compounded: in Peano, as we take more actions, available actions also increase (growing set of existing objects)�
• Probability of making progress by exploration decays exponentially as solutions increase

67

How do humans do it?

Assuming:

How do you do / explain this solution?

Not 10 steps, but only 3!��(1) observe you can subtract from both sides (new)�(2) CLT on the left-hand side�(3) SEE on the right-hand side

Hypothesis: After enough exercises, a student will internalize procedural abstractions that make it easy to construct solve more complex problems

How can we learn abstractions?

Extend Peano with procedural abstractions, or “tactics”, that apply a sequence of axioms or other tactics (akin to a symbolic skills / macro-actions)

Tactics can be induced by noticing patterns in solutions found so far – compress solutions by anti-unifying overlapping traces

69

ConPoLe + abstraction

70

Compress the successful solutions by inventing new tactics

Solve a batch of random problems (using beam search with the current policy)

Train the policy to imitate successful trajectories (re-written with new tactics)

ConPole + Abstractions

​

71

Abstractions let the agent�make steady progress,�eventually solving all problems.

Related recent approaches

This work: ‘Chain of thought’ policy. Generation constrained by formalism. Abstraction learning. No data, no pre-training.

STaR: Self-Taught Reasoner (Zelikman, etal, 2022)

Minerva (Lewkowycz, etal, 2022)

DreamCoder (Ellis, etal, 2020)

(Several great posters today!)

72

Curricula

Even mathematics that takes centuries to develop can be taught quickly to next generations

Some of this acceleration comes from a curriculum�

Training problems were seen in random order

Solutions with tactics can be ordered by the dependencies between their tactics

Topological sort on problems gives a curriculum

73

Abstraction-based curriculum

74

Abstraction learning is�synergistic with curricula:�a good ordering leads to�useful tactics faster

Derived vs expert curriculum

Permutation distance to Khan Academy is significantly lower than a random problem ordering.��Abstractions reveal part of how we structure our educational curricula