STaR: Bootstrapping Reasoning With Reasoning
- Publication
- NeurIPS 2022Conference
- First submitted to arXiv
- arXiv:2203.14465
Cite this paper · BibTeX
The citation identifies the linked source version. It cites the original paper and its authors.
@misc{modeltuningstar2022,
title = {{STaR: Bootstrapping Reasoning With Reasoning}},
author = {Eric Zelikman and Yuhuai Wu and Jesse Mu and Noah D. Goodman},
year = {2022},
eprint = {2203.14465},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2203.14465}
}
By early 2022 there was already plenty of evidence that models answer better when they write out their reasoning before the answer. The question was how to get a model to learn to write that reasoning.
There were two routes at the time. One was to prepare a large batch of training data with worked reasoning and fine-tune on it. That takes people writing it out one question at a time, as in CoS-E, the dataset of human explanations for CommonsenseQA; or you generate it automatically from templates, which only works for problems whose solution is known and can be written as rules.
The other was chain-of-thought prompting: put a few examples with reasoning in the prompt, no training required. It's cheap, but it usually falls short of a model trained directly on lots of data to "output only the answer." Take GPT-J 6B, the model this paper uses. On CommonsenseQA, few-shot chain of thought gets only 36.6%, while fine-tuning it to output the answer directly gets 60.0%.
Zelikman et al. at Stanford wanted to take a middle road. Prepare only ten or so examples with reasoning, plus a large batch of questions with answers but no reasoning, and have the model write reasoning for itself to learn from.
Defining the problem
You have a pretrained model , a dataset that has only questions and answers, and a small set of examples with reasoning, , about 10 of them.
The goal is to train a model that writes reasoning first and then the answer , and that is more accurate than a model that only outputs the answer.
The whole method rests on one assumption, that reasoning which leads to the correct answer is of higher quality than reasoning that leads to a wrong one. This assumption doesn't always hold, and we'll come back to it later.
Solving the problem

Write your own reasoning, keep only what's right
The first step is straightforward. Use those ten or so examples as the prompt and ask the model to write reasoning and an answer for every question in the dataset. Where the answer matches the reference answer, keep it along with the reasoning; where it's wrong, throw it away.
Then fine-tune the model on what was kept, use the fine-tuned model to work through all the questions again, filter, fine-tune, and keep repeating until the scores stop improving.
Every round of fine-tuning starts again from the original pretrained model rather than continuing from the previous round's model, to avoid overfitting. The first round trains for only 40 steps, and each round after that adds 20%. The authors found that training more slowly at the beginning led to better final scores.
For questions it can't solve, show it the answer
Keeping only the questions the model got right has an obvious problem. Questions the model can't solve never make it into the training data, and once it has learned everything it can already do, it has nothing new to learn.
The authors' fix is called rationalization. For questions the model got wrong, tell it the correct answer directly in the prompt and ask it to write the reasoning:
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
A: The answer should be the place where grocery items are placed before
checking out. Of the above choices, grocery cart makes the most sense for
holding grocery items. Therefore, the answer is grocery cart (b).
A prompt example from Figure 2 of the paper; the "(CORRECT)" is the hint given to the model.
Once you know the answer, it's much easier to work backward to a plausible justification. Then, when this reasoning goes into the training data, the hint is removed, and the training input is just the original question, as if the model had come up with the reasoning on its own.
That way, hard questions the model couldn't solve also get into the training data, and the amount of data grows along with them.
The full algorithm is two nested loops:
- Use the current model to write reasoning and an answer for every question.
- For questions it got wrong, add the correct answer as a hint and write again.
- Keep the ones answered correctly in step 1, and the ones that reached the correct answer with the hint in step 2.
- Starting from the original , fine-tune on this data to get , then go back to step 1.
This is actually reinforcement learning
The authors point out that STaR can be viewed as an approximation of reinforcement learning. Treat the reasoning as a latent variable, give 1 point for a correct answer and 0 for a wrong one, and the expected reward over the whole dataset and its gradient are:
This is the standard policy gradient. Samples with a wrong answer get a reward of 0, so their gradient simply vanishes, which is exactly STaR's "keep only what's right." For samples with a correct answer, the gradient is the ordinary log-likelihood gradient, which amounts to supervised fine-tuning on them.
Compared with a true policy gradient, STaR makes two simplifications. It uses greedy decoding instead of random sampling, which lowers the variance at the cost of less exploration, and it takes many gradient steps on the same batch of data. Rationalization can be seen as sampling from a different distribution, , which makes it an off-policy estimate.
At the time, this derivation was just a side remark. Later it became a handy angle for understanding how reasoning models are trained.
Experimental setup
- Model: GPT-J 6B, because its weights and fine-tuning code are public, and it's big enough to write reasoning of some quality. The batch is 8 sequences of length 1024, the learning rate is , and training and sampling run on a single TPU v3 node.
- Addition: adding two -digit numbers, with the digit-by-digit working written out in the scratchpad format of Nye et al. They first generate 50,000 problems and sample 10,000 of them each round; there are 10 examples for each digit length from 1 to 5.
- CommonsenseQA: five-way multiple-choice commonsense QA, with 9,741 training questions. The prompt uses the 10 questions from the chain-of-thought paper; the authors fixed a wrong answer in one of them and made the reasoning cite the relevant knowledge more explicitly.
- GSM8K: grade-school math word problems, with 7,473 training and 1,319 test problems.
The reasoning for the addition problems follows the format of Figure 3 in the paper, adding digit by digit starting from the ones place, with C as the carry. Take 624 + 259 as an example:
<scratch>
6 2 4 + 2 5 9 , C: 0
2 + 5 , 3 C: 1
6 + 2 , 8 3 C: 0
, 8 8 3 C: 0
0 8 8 3
</scratch>
8 8 3
Each line holds the next pair of digits to add, the result accumulated so far and the carry. The model has to learn to write everything from <scratch> through the final answer on its own; during rationalization, the correct answer goes after "Target:" in the prompt.
In this format the reasoning and the answer are tightly bound. Get one step of the reasoning wrong, and the answer is almost certainly wrong. That matters a lot later on.
Discussion
Addition: climbing one digit at a time

The starting point is extremely low. With few-shot prompting, GPT-J's accuracy on 2-digit addition is under 1%, and with more digits it's close to 0.
Without rationalization (left), progress comes in stages. The model has to get good at digits before digits start to improve, and 5 digits has to wait until around iteration 23. That makes sense. Only correctly answered questions get into the training data, so the model first has to get the occasional -digit question right before it has anything to learn from.
With rationalization (right), all digit lengths improve almost together, just to different accuracies. After the first round of fine-tuning, 2-digit addition jumps from under 1% to 32%. Because of the hint, many problems can be solved few-shot, so this run starts training with 300 steps and adds 20 steps per iteration.
The paper reports an overall accuracy of 89.5% after 16 iterations. For comparison, a model trained for 5,000 steps on 10,000 problems without writing any reasoning reaches 76.3%.

The authors also added problems with more digits around iteration 20, keeping the total number of training problems the same. The original 1 to 5 digits actually improved faster, and the model could also get some 9- and 10-digit problems right, even though they never appeared in training. The price is that training became unstable, and the authors can't say exactly why.
CommonsenseQA: 6B catches up with 175B
| Method | Accuracy | Train data used |
|---|---|---|
| GPT-3 175B fine-tuned to answer directly | 73.0 | 100% |
| GPT-J few-shot, direct answer | 20.9 | ~0 |
| GPT-J few-shot chain of thought | 36.6 | ~0 |
| LaMDA 137B few-shot chain of thought | 55.6 | ~0 |
| GPT-J fine-tuned to answer directly | 60.0 | 100% |
| STaR (no rationalization) | 68.8 | 69.7% |
| STaR (with rationalization) | 72.5 | 86.7% |
Compiled from Table 1 of the paper; accuracy is on the dev set, in %. Of the 86.7% in the last row, 78.2% comes from questions the model got right on its own and 8.5% from rationalization.
A few things in this table are worth comparing:
- Using only reasoning that GPT-J wrote itself, STaR scores 8.8 percentage points higher than fine-tuning directly on all the data, and it only uses 70% of the questions.
- Adding rationalization brings it to 72.5%, just 0.5 behind the 73.0% from fine-tuning GPT-3, a model nearly 30 times larger.
- Few-shot chain of thought on the small model gets only 36.6%; STaR lifts it by 35.9 percentage points, which also beats few-shot chain of thought on LaMDA 137B.
Random guessing on a five-way multiple-choice question already gets 20%, and the authors also note that simple heuristics such as semantic similarity alone can reach around 30%.
Another finding is that including those few-shot examples in the training sequences during fine-tuning helps noticeably. Without rationalization, the score goes from 60.9% to 68.8%; with rationalization, from 69.9% to 72.5%.
The quality of the reasoning
For addition, you can judge the reasoning by comparing it directly with the reference working. For commonsense questions, all you can do is have people read it. The authors randomly picked 50 questions that both few-shot chain of thought and STaR had answered correctly, and pulled the human-written explanations for them from CoS-E. Twenty crowdworkers each looked at 10 questions and ranked the three kinds of reasoning.
STaR's reasoning was 30% more likely to be ranked above the few-shot reasoning (), and 74% more likely to be ranked above the human-written explanations (). The authors make a point of saying that this reflects how hard it is to get people to write high-quality explanations in the first place; the model's ability to write reasoning is not yet at human level.
Even with the right answer, though, the reasoning can be hollow. The appendix lists several types of reasoning that land on the correct answer but don't hold up. The most common one simply restates the question and passes it off as a reason:
Q: What might someone get from learning about science?
Answer Choices:
(a) headache
(b) see things differently
(c) increased knowledge
(d) accidents
(e) appreciation of nature
A: The answer must be something that someone would get from learning about
science. Learning about science would increase knowledge. Therefore, the
answer is increased knowledge (c).
An example from Appendix A.1 of the paper.
"Learning science increases knowledge, so the answer is increased knowledge." That isn't wrong, but it doesn't explain why the answer isn't "appreciation of nature" either. Other types include circular reasoning, giving no reason at all, and treating a name in the question as a real person, producing reasoning like "James would feel exhilaration from heights."
GSM8K: low in absolute terms, doubled in relative terms
| Method | Test accuracy | Train data used |
|---|---|---|
| GPT-J few-shot, direct answer | 3.0 | ~0 |
| GPT-J few-shot chain of thought | 3.1 | ~0 |
| GPT-J fine-tuned to answer directly | 5.8 | 100% |
| STaR (no rationalization) | 10.1 | 25.0% |
| STaR (with rationalization) | 10.7 | 28.7% |
Compiled from Table 2 of the paper; values are in %.
Grade-school math is hard going for the 6B GPT-J, and STaR only reaches 10.7%. Still, that's nearly double the 5.8% from direct fine-tuning, using only about a quarter of the problems. Here rationalization barely helps; of the 28.7% of the data used, only 0.5% comes from rationalization. The number of training steps also had to be capped, or training would have run too long. In the end it ran 36 iterations, plus another 10 with rationalization.
The authors compared the number of calculation steps the model used with the number in the reference solutions; they matched between 53% and 57% of the time. When they didn't match, the model usually used fewer steps. Sometimes it skipped steps, and sometimes it found a different solution. The appendix has a problem whose reference solution takes 7 steps, which the model solves in one step by skipping the redundant information.
Why not just sample more?
The most intuitive way to expand the training data is to raise the temperature and sample a few more times; some of the samples are bound to be right. The authors tried this, and it made things worse.
At higher temperatures, there are more samples where "the reasoning is wrong but the answer happens to be right," and training on that kind of data teaches the model nothing that generalizes. It's especially clear on addition. The scratchpads learned from high-temperature samples gradually turn meaningless, and the model gets stuck. Versions at temperature 0.5 or 0.7 were consistently worse than STaR without rationalization. On top of that, sampling 10 times is about 10 times slower, much more expensive than rationalization.
The share of "lucky guesses" depends heavily on how easy the question type is to guess. Suppose the model's reasoning is actually correct a fraction of the time, and when the reasoning is wrong it still guesses the answer with probability . Then among the data that passes the "correct answer" filter, the share whose reasoning is actually wrong is
Multi-digit addition is almost impossible to guess, so is close to 0 and the filter is clean. For five-way CommonsenseQA, if you estimate with the random-guess value , then at the start, with , about 64% of the kept data is lucky guesses; when rises to 0.6, that falls to about 12%. Yes/no questions have , which is even worse. The share drops as the model gets stronger, but the data is of the worst quality at the start, which is exactly when it matters most.
Limitations
The authors raise these points in the conclusion and appendix:
- The starting point can't be too weak: for the first round to work, few-shot performance has to be above chance, so the model must already have some reasoning ability. The authors tried GPT-2, and it couldn't even get started on addition.
- Tasks that are easy to guess: tasks like yes/no questions leave behind a lot of bad reasoning, and how to filter it is still an open question.
- Biases get amplified: STaR amplifies reasoning that "gets the right answer," so if biases in the dataset help get the right answer, those biases get amplified too. Rationalization goes further and "pulls out" biased answers the model wouldn't have given on its own.
- The reasoning isn't necessarily faithful: the model may pick the answer first and then make up a justification. That kind of reasoning has nothing to do with what the model actually based its decision on, and STaR has no way to check for it.
- Hints aren't always easy to give: here the hint is just the correct answer, but in other settings it may not be so obvious how to give one.
The authors also suggest an extension: sample several lines of reasoning at high temperature, vote on the answers, and treat the majority answer as the reference answer. That way even questions without answers could be used for training.
What came after
STaR's loop was later scaled up several times. In December 2023, Google DeepMind's ReSTEM applied the same approach to PaLM 2 on MATH and the APPS coding problems: sample, filter by whether the answer is right, fine-tune, repeat for a few rounds. It re-derived the method from the angle of expectation-maximization (EM), and the result beat fine-tuning on human-written data alone.
In March 2024, the authors themselves proposed Quiet-STaR, which moves "think before you speak" into pretraining. On ordinary web text, the model generates a short piece of internal reasoning after every token and uses it to predict the text that follows. After continued pretraining on OpenWebMath and C4, Mistral 7B, with no task-specific fine-tuning, rose from 5.9% to 10.9% on GSM8K and from 36.3% to 47.2% on CommonsenseQA.
As for that policy-gradient derivation, it turned into real reinforcement learning in reasoning models. DeepSeek-R1's rewards are rules of the "is the answer right?" kind. When it collected supervised fine-tuning data after reinforcement learning, it sampled several responses per prompt and kept only the correct ones, collecting about 600,000 reasoning samples in all. That's the same filtering as STaR, several orders of magnitude larger.
Conclusion
With only 10 examples with reasoning plus a batch of questions that have only answers, STaR gets GPT-J 6B to write thousands of lines of reasoning and train itself on them. It reaches 72.5% on CommonsenseQA, just 0.5 percentage points behind a directly fine-tuned GPT-3 nearly 30 times its size.
The cleverest part is rationalization. For questions the model can't solve, tell it the answer first and let it work backward to a reason, then hide the answer during training. Hard questions can get into the training data this way, and all the digit lengths in addition can improve together instead of waiting their turn one stage at a time.
Its weakness is just as clear. The filter looks only at the answer. For question types where the answer is easy to guess, a large share of the reasoning that survives may be cobbled together, and the paper never solves this. Later reasoning models used bigger models, more samples and stricter verification to spin this loop bigger and bigger, and that original problem is still sitting there.