NeurIPS 2022 (Oral)

STaR: Self-Taught Reasoner

Bootstrapping Reasoning With Reasoning

Eric Zelikman*¹, Yuhuai Wu*^1,2, Jesse Mu¹, Noah D. Goodman¹

¹Stanford University, ²Google Research | *Equal Contribution

TL;DR

"STaR is a simple, iterative loop that lets a large language model learn to reason by training on its own generated rationales. By filtering out incorrect answers and using 'rationalization' to reason backward for failed tasks, a 6B model bootstraps itself to match a 30× larger fine-tuned model."

#Reinforcement-Learning #Chain-of-Thought #Self-Improvement #Rationalization

Why This Matters

Large language models (LLMs) are highly capable pattern matchers, but they struggle with multi-step logical tasks like math word problems or complex commonsense reasoning. Recent work shows that prompting models to generate intermediate reasoning steps—known as Chain-of-Thought (CoT)A prompting technique that encourages the model to output intermediate reasoning steps before the final answer. or rationalesAn explicit justification or step-by-step logic explaining why an answer is correct.—substantially improves performance.

However, we face a major bottleneck: how do we get high-quality rationale training data?

Human Annotation is Expensive

Writing thousands of step-by-step explanations for every new task domain requires immense manual effort and does not scale easily.

Few-Shot Limits Performance

Using only a few rationale examples in the prompt at inference time is highly sensitive to prompt design and underperforms fully fine-tuned models.

STaR solves this by letting the model generate its own training data. By using a small seed of human-written rationales, the model bootstraps its reasoning ability on a large dataset of questions without human-written explanations.

The Big Idea

The core contribution of STaR is a synergistic, iterative loop: better reasoning leads to better training data, and better training data leads to better reasoning.

"If a model generated a rationale that ultimately led to the correct answer, that rationale is likely correct. We can filter out the bad rationales by checking the final answer, and fine-tune the model on the successful ones."

But what about the problems the model gets wrong? If the model cannot solve a problem, it cannot generate a correct rationale, receiving no training signal. To overcome this, STaR introduces Rationalization: when the model fails, we provide it with the correct answer as a "hint" and force it to reason backward. Once it generates a valid backward justification, we add it to the training set as if the model had come up with it without the hint.

How It Works

STaR operates in a continuous loop of generation, filtering, rationalization, and fine-tuning. Let's explore the math and the algorithm visually.

The Policy Gradient Connection

STaR can be viewed as an approximation to a reinforcement learning policy gradient objective. If we treat the rationale $r$ as a discrete latent variable, the expected reward is:

$$J(M, X, Y) = \sum_{i} \mathbb{E}_{\hat{r}_i, \hat{y}_i \sim p_M(\cdot|x_i)} [\mathbb{I}(\hat{y}_i = y_i)]$$

Taking the gradient using the log-derivative trick yields:

$$\nabla J(M, X, Y) = \sum_{i} \mathbb{E}_{\hat{r}_i, \hat{y}_i \sim p_M(\cdot|x_i)} \left[ \mathbb{I}(\hat{y}_i = y_i) \cdot \nabla \log p_M(\hat{y}_i, \hat{r}_i | x_i) \right]$$

The indicator function $\mathbb{I}(\hat{y}_i = y_i)$ acts as a hard filter, discarding gradients from rationales that lead to incorrect answers.

1 Interactive STaR Loop Simulator

Simulate how the training dataset grows and the model accuracy improves across iterations. Compare STaR with and without Rationalization.

Method Mode

Iteration 1 / 5

Total Questions: 10,000

Direct Correct: 2,090

Rationalized: 1,570

Fine-tuning Set Size: 3,660

Model Accuracy (CommonsenseQA) 36.6%

Step 1: Generate

CoT Rationales

Prompted with 10-shot examples

Step 2: Filter

Keep Correct

Discard wrong final answers

Step 3: Rationalize

Backward Hint

Force justification for failed Qs

Iteration 1: Starting with few-shot prompting. The model solves 20.9% directly. Rationalization adds extra backward-reasoned rationales for the rest.

2 Rationalization Sandbox (Backward Reasoning)

See how adding a "hint" helps the model generate a correct rationale that it otherwise failed to discover.

Question (CommonsenseQA)

"Where do you put your grapes just before checking out?"

(a) mouth (b) grocery cart (c) super market (d) fruit basket (e) fruit market

Direct Rationale Gen FAILED

# Model attempts to answer without help

A: Grapes are fruit. You find fruit at a fruit market. Therefore, the answer is fruit market (e).

❌ The answer is incorrect. This rationale is discarded and cannot be used for fine-tuning.

Rationalization (With Hint) SUCCESS

Prompt Hint: The correct answer is (b) grocery cart.

A: Grapes are grocery items. You place grocery items in a grocery cart before paying at checkout. Therefore, the answer is grocery cart (b).

✅ The answer matches the hint! We strip the hint and save this rationale to the fine-tuning dataset.

3 Symbolic Reasoning: Arithmetic Scratchpad Player

Step through how a STaR-trained model uses an internal "scratchpad" to calculate multi-digit addition, tracking carry operations explicitly.

Select Problem

Input: 29 + 45

Click "Play Steps" to begin execution.

Results & Benchmarks

STaR was evaluated on multiple challenging datasets: CommonsenseQA (CQA), GSM8K (grade-school math word problems), and Arithmetic.

The results demonstrate that STaR allows a 6B GPT-J model to perform on par with much larger models, even matching a 175B GPT-3 model fine-tuned on the same data.

Performance Comparison

Compare accuracy across different models and training strategies.

* CoT denotes Chain-of-Thought prompting. Source: STaR Paper Table 1 & Table 2

Limitations & Open Questions

While STaR is a powerful framework for bootstrapping reasoning, the authors note several limitations and areas for future work:

The "Cold Start" Problem: STaR requires the initial base model to have some baseline few-shot reasoning capability. For instance, the authors found that GPT-2 was too small to bootstrap itself because its initial few-shot accuracy on arithmetic was 0%.
High Chance of Success Bias: In binary classification or multiple-choice settings with few options, the model might guess the correct answer by chance using a completely flawed rationale. Filtering purely on the correctness of the final answer can pollute the training set with bad logic.
Rationale Faithfulness: It is difficult to guarantee that the model's generated rationale actually reflects its internal decision-making process. The model might perform "post-hoc rationalization"—choosing the answer first and then generating a plausible-sounding but unrepresentative justification.

Glossary

Bootstrapping

A self-sustaining process where a system improves its own capabilities iteratively without requiring external training data or extensive human intervention.

Chain-of-Thought (CoT)

A technique where models are prompted or trained to output intermediate steps of reasoning before producing the final answer, significantly improving accuracy on multi-step tasks.

Rationalization

The process of generating a rationale backward, conditioned on both the question and the known correct answer. This helps the model discover reasoning paths it failed to find in forward generation.

Expert Iteration (ExIt)

A reinforcement learning method where a fast "apprentice" model learns from a slower, more capable "expert" search process, iteratively replacing the expert with the improved apprentice.

Citation

@inproceedings{zelikman2022star,
  title={STaR: Bootstrapping Reasoning with Reasoning},
  author={Zelikman, Eric and Wu, Yuhuai and Mu, Jesse and Goodman, Noah D},
  booktitle={Advances in Neural Information Processing Systems},
  year={2022}
}