Title: Part 5 Planning and Multi-Step Reasoning
Authors/Date: Akanksha Bhardwaj, Azalia Mirhoseini — Stanford CS329A
Video ID: Ml_fp9XkB8Y  |  URL: https://www.youtube.com/watch?v=Ml_fp9XkB8Y
Playlist: https://www.youtube.com/playlist?list=PLangBM27OtEA
------------------------------------------------------------------------

0:05 So today's lecture is going to
be about planning and multi-step
0:10 reasoning.
0:11 So today's lecture, we are
going to cover three papers
0:14 on multi-step
reasoning and planning.
0:17 Let's start with this paper
from ICML of last year.
0:26 So the title of the paper is
Language Agent Tree Search
0:32 Unifies Reasoning Acting and
Planning in Language Models.
0:37 So the types of
applications that we
0:43 want to target in
multi-step tasks
0:46 are tasks that we not only
need to reason about things,
0:50 but also need to act through
those reasoning steps
0:53 and search our trajectories,
or optimize trajectories
0:59 and how we get to a
final correct answer.
1:02 So in the reasoning
step, the model
1:04 needs to think about
what needs to be done?
1:08 For example, what the budget
is, where the plan is.
1:11 These are the reasoning steps
for a trip or vacation planning
1:15 prompt.
1:17 The act is OK.
1:19 Now that you have certain
types of reasoning or thinking,
1:24 how do you gather
more information,
1:26 or act on these reasoning steps?
1:28 For example, the action
could be a browsing
1:32 the web, generating
a query to search,
1:36 read Reddit, or a
travel blog, and so on.
1:40 And then another step is search.
1:45 Given these feedback,
or the information
1:47 that's gathered online, how
can we refine our plan so far?
1:55 Maybe we can consider
alternative destinations, search
1:59 new things to do while
we are there, and so on.
2:02 So there are a series of
reasoning, action, and search
2:07 steps that needs to be done
to solve this problem of,
2:11 for example, planning a trip.
2:13 So the problem, or the challenge
that this paper specifically
2:17 wanted to address
was the following.
2:23 The goal here was, let's go
from the LLM, generate a plan,
2:27 and executing on that
plan, to really try
2:31 to encourage diversification and
exploration of different types
2:36 of plans, or paths that the
model can take because models--
2:42 And this is true still
to this day, that
2:47 creating a diversity of
solutions, or acting upon them
2:51 and planning multiple
steps of optimization
2:55 to reach a solution.
2:58 So this paper focused on
bringing known techniques
3:01 from reinforcement learning
and multi-step planning that
3:06 existed in the past, including
multi-step Monte Carlo tree
3:11 search into the
LLM reasoning path.
3:16 And given that the models
can take feedback in,
3:21 it also introduced
ways for the model
3:24 to take different feedback
as the model explores
3:27 with the environment
and bring that back
3:30 in order to refine and optimize
future plans and search
3:35 processes.
3:39 So just a quick example
of how this worked.
3:47 For example, the prompt is
to plan a trip to Hawaii.
3:51 There are different ways
and different actions
3:53 that the model can take,
so it can, for example,
4:00 if we sample the
model for this prompt,
4:03 the model might decide
that we might consider
4:07 asking friends that
already went to Hawaii,
4:10 or read subreddits
related to that.
4:13 And then this framework
introduced a mechanism
4:17 for getting a score for
each of these actions,
4:22 and then update the search
space, or the trajectory
4:26 of follow-up expansion of
this tree that is being
4:30 formed based on that score.
4:33 And we talk about how
these scores are generated.
4:36 In this case, action
1 has a higher score,
4:39 so we expand that action, so
the model expands that action.
4:44 So in this case, ask two
friends, friend a and friend
4:49 b, about opinions,
and then based
4:51 on the quality of responses,
their score for that,
4:55 and the model can
expand from there,
5:00 so there is a flavor of
multi-action sampling
5:05 in this case.
5:06 The actions can, in fact,
be executed in parallel.
5:09 Like these two actions,
or these two actions,
5:12 they both can be
executed in parallel.
5:15 And there's this notion of let's
do continuous exploration based
5:20 on the best state,
but also consider
5:24 a mix of exploration
and exploitation,
5:27 and that's where
the MCTS comes in.
5:33 So there are two papers that--
5:37 this paper was basically saying,
how it diverges from those.
5:41 Math-Shepherd is a paper
that we saw previously,
5:45 and in that paper,
there was a verifier
5:47 that was guiding the search
process in the test time.
5:51 Basically, the
reasoning trajectories
5:56 are scored by this verifier,
and then the expansion
6:02 is guided by that.
6:04 But in LATs, which
is this paper that we
6:06 are going to learn more
about in this lecture,
6:11 this scoring is not based
on reasoning theorists,
6:14 but it's based on the
outcomes of the actions
6:17 that the model takes.
6:19 And also there is this part
about reflection of the model
6:23 to evaluate how this
trajectory went,
6:27 and also about the observations
from the environment.
6:32 It also improves based on
previous methods frameworks
6:38 on reasoning such as the ReAct
work, where basically in ReAct,
6:50 there is this extra step up.
6:52 We are going to
see how this works,
6:54 but there is this extra step
memorization, and, again,
6:57 reflection and an interaction
with the environment
7:00 that we have in the LATs paper.
7:03 And specifically, we
have more and more
7:06 planning into the process.
7:11 So here is the
intuition behind LATs.
7:17 There is the chain of
thought, where the reasoning
7:22 process is basically decomposed
into a number of steps.
7:26 There is this notion
of tree expansion.
7:30 Basically, through these
types of actions, that action
7:35 generation that we have, we have
a tree, that we form a tree,
7:39 and we do search and
planning through that.
7:41 And then we have
this borrowed that
7:44 from the ReAct framework, where
the feedback from these actions
7:49 are incorporated
into this search
7:52 process for the future
search and so on.
7:57 So this method concretely has
six types of stages, selection,
8:08 expansion, evaluation,
simulation, back propagation,
8:12 and reflection, so let's see
exactly how this method works.
8:16 And let's walk through
an example prompt.
8:20 So in this case, the prompt
is navigate through a maze
8:25 to reach an exit.
8:27 And then the initial
observation is
8:29 that you're in a
dimly lit room, there
8:31 are two doors, one on the
left and one on the right,
8:34 and the goal is to reach
an exit in this case,
8:38 so let's see how these different
steps of LATs come into play.
8:44 So first is the
selection process.
8:46 In this stage, we need to
select a node to expand.
8:50 Let's say, we have done that.
8:51 We see exactly how
that's done, but given
8:59 that we have selected a node,
and this is based on UTC,
9:02 we are going to
see it in a bit, we
9:04 want to see what actions that
we can take from that node.
9:08 So in this case, our
initialize node is this thing,
9:13 you're in a dimly
lit room and so on.
9:16 Now, let's say, the model
samples different actions here.
9:21 In this case, three
actions are sampled.
9:23 One is open the left
door, open the right door,
9:26 and the third one is
inspect the room for clues.
9:29 Then the next step is
each of these actions
9:32 are executed in the environment,
and the observation is basically
9:36 appended to the context.
9:40 So in this case, say, if the
action is open the left room,
9:45 the observation is dark
corridor with paintings.
9:48 Action B is open the right.
9:50 There is another observation
and so on for action C.
9:54 Now comes the evaluation.
9:57 So let's say, we have an action,
we have executed an action,
10:01 we want to evaluate our new
state that we are going into.
10:05 For this part, they suggest
averaging for creating a score.
10:11 Based on the current
action and observation,
10:16 they suggest adding up
two scores together.
10:19 One is using an LM score,
basically using LLM-as-a-Judge
10:25 and prompting the model for
evaluating how promising this
10:30 state is, and literally asking
it to give a score based on 0
10:34 to 1 for this state.
10:36 And the other one is the
self-consistency score.
10:39 And that is, let's assume
instead of three actions here,
10:43 we had sampled 50 times.
10:48 We had sampled 50 actions,
and we categorized them
10:51 into different types of actions.
10:53 And if an action
is sampled more,
10:58 we give a score
corresponding to the rate,
11:01 or the frequency of an
action being sampled.
11:04 So in this case, the
self-consistency score
11:07 for state A was higher because
75% of the time maybe the action
11:12 was sampled, so the
way to create just one
11:18 value for this action
is to add up these two.
11:22 So now we have a value
for action A corresponding
11:26 to state s_A.
11:31 And then we have
the simulation part.
11:34 For example, in a greedy
method from the previous stage,
11:38 we have s_A having
the highest score.
11:41 s_B and s_C have
much lower scores,
11:44 so we go and expand
s_A all the way begin.
11:49 We can continue this process.
11:50 We sample more from s_A
and we continue expansions
11:54 until we reach an end state,
or whether it's successful,
11:59 or it fails, or until we
reach the budget that we have
12:04 for expansion of this state.
12:07 So in this case,
from state s_A--
12:11 so this was s_A, and then we
have the candidate actions
12:16 that start from that state.
12:18 And then in this
case, it's greedy.
12:20 It takes one action
approach, this staircase,
12:26 and then we reach an
observation, which
12:30 we are lucky in
this case, we have
12:32 the exit door clearly marked.
12:34 We got a point here.
12:38 And then let's say the
simulation is done.
12:43 We either have a
successful trajectory
12:45 or it's a failure, then we can--
12:49 the important part
here is how do we
12:52 use this observation
to backprop and update
12:56 the scores that we had
for different actions
12:58 that were taken?
13:00 So this is the backprop
stage, and then
13:02 that is used to influence
the score of each state,
13:09 and we're going to
talk about it in a bit.
13:11 Let's talk about how these value
function and backpropagation
13:15 is used.
13:15 So for the value function,
we already saw that.
13:19 That is a weighted average of
asking an LLM-as-a-Judge given
13:23 this observation, this action,
what are the chances of success?
13:27 Give us a score between 0 to 1.
13:29 And then there is
the self-consistency,
13:31 which basically we just count
how many times a given action is
13:36 sampled.
13:38 Then there is the notion of
UCT, or upper confidence bounds
13:43 applied to trees.
13:44 That's something that this
basically the number, or score
13:50 that is used for selection
because at each point,
13:54 we have a range of values
that we want to see,
13:57 which node we go and expand.
13:59 So the way UCT works, and
this is completely borrowed
14:03 from the MCTS literature.
14:08 The way it's designed is to try
to balance between exploration
14:12 and exploitation.
14:13 If we just go based on the
highest value at that point,
14:17 we might miss out other
nodes that right now, maybe
14:20 at the current moment
have a lower value,
14:23 but down the road
at the end might
14:25 have higher value, so let's
balance the two of them.
14:29 So the way UCT works is that it
has this exploitation one, which
14:34 is V of s, plus
a hyperparameter,
14:37 times this other term, which
encourages exploration.
14:41 And the way this work
here is that the Np is
14:45 the number of times a
parent of a node is visited,
14:48 and Ns is the number of nodes
that this current node is,
14:52 not the parent, but the
current node is visited.
14:54 And basically, think
about it this way.
14:57 Relative to the parent node,
if a node is visited less,
15:01 we want to encourage
visiting that node more.
15:04 And if that node
relative to the parent
15:06 is visited a large
number of times, then
15:11 this number, this division, this
becomes a smaller number and UCT
15:16 becomes lower relative to
unexplored children of a parent
15:23 node.
15:24 So UCT, again, is the number
that we use for selection
15:30 of a node and going from there.
15:32 Now, back propagation,
and that's
15:34 where we go at the
end of a trajectory,
15:38 either we succeed or fail.
15:40 The return of that trajectory
is used to update the values,
15:44 and this is like back
propagated through the steps.
15:47 So at each point,
the value of a state
15:51 is the value of the old state,
times the number of visits
15:56 to that node, minus
1, plus the return,
16:00 divided by the total number
of visits to that node.
16:02 So that's how the math
behind this framework.
16:07 Yes.
16:09 Why does it have one [INAUDIBLE]
you take a long time,
16:17 but it didn't take long?
16:19 It's just something.
16:20 There's some math and
theoretical intuitions
16:23 behind it.
16:24 There is no proof that
this is the optimal round,
16:27 but you want to just
balance the two in that this
16:31 is considered a more
optimized way of doing things.
16:35 [INAUDIBLE]
16:37 Yes.
16:43 So once backpropagation
is done, they also
16:49 append this reflection
of the model itself
16:52 about the trajectory
that was expanded.
16:56 If it fails or it
succeeds, the model
16:58 adds some thinking
behind what happened,
17:01 what led to the failure or the
success of this trajectory,
17:06 and this apparently
has been very
17:07 helpful in overall increasing
the quality of this approach.
17:14 So they tested this
approach on HotPotQA,
17:17 which is some data set that we
use it for multi-step reasoning
17:23 optimization.
17:24 Basically, the way
this data set works
17:26 is that for each question
for answering them,
17:30 you need retrieval from, at
least, two different Wikipedia
17:33 pages because it's just
designed like that,
17:37 so you need this multi-step
by design process
17:40 in order to find an answer.
17:42 And they're doing really well.
17:46 Just look into in terms
of as they increase
17:49 the number of samples or
the number of trajectories
17:52 that they sample,
they can significantly
17:55 improve performance,
and the reflection
18:01 and bringing those reasoning
traces also gives a lot of boost
18:05 at the end to the model.
18:06 So basically, they have
provided a mechanism
18:09 to translate more
compute at test time
18:13 effectively to better solutions
for this multi-step reasoning
18:18 tasks.
18:19 They also tested
that on WebShop,
18:21 which is this interesting data
set for practical applications.
18:33 This is just to
show you an example
18:35 of how this data set works.
18:37 For example, there is--
18:38 I'm looking for a small
portable folding desk
18:41 that's already fully assembled.
18:43 It should have this color
and this finish and so on,
18:46 and the price is--
so it's by design,
18:50 it's a multi-step
process, and they're
18:54 showing that their approach
without any fine tuning.
18:57 And just at test
time, they can get
18:59 really high results, even close
to human experts in this case.
19:09 So to summarize,
what LATs proposed
19:12 was a new technique for
bringing in reasoning,
19:17 taking actions and
planning all together,
19:19 and brought in our
known ideas like MCTS
19:23 into the language model world.
19:27 And they got very strong
results on multiple domains.
19:31 And given their
test time approach
19:35 and the modular approach,
it's very portable
19:38 and relatively easy to create.
19:42 The downside, of
course, is the cost.
19:47 Each of these back
propagation and expansion
19:50 of a tree, all of those
are adding a lot of cost,
19:53 and the cost benefits was not
really analyzed in the paper.
20:00 Another assumption that
this paper didn't address
20:04 was really that
there are scenarios,
20:07 where taking an action
may be irreversible.
20:10 So that's going to
be challenging like,
20:12 how do we adapt to
those scenarios,
20:15 if, for example, the model
is running a transaction?
20:19 If it actually
takes those actions,
20:21 it could be very consequential,
like paying for a service
20:24 and so on.
20:25 So that is another scenario,
where this approach might not
20:31 be adaptable to.
20:35 So here, there are
a few questions
20:36 about this paper that I really
would like you to think about it
20:41 maybe for a couple
of minutes, and then
20:42 we discuss anything related
to where you see the strengths
20:47 or weaknesses of
this paper, or if you
20:49 were to adapt it or extend
it, how would you do that?
20:55 So let's start doing that,
and I'll get back to you
20:58 in a couple of minutes.
21:03 All right, let's get back.
21:05 Anyone wants to
comment on this fork?
21:09 So the UCT method is basically
like upper confidence-bound
21:14 from banded learning
setting, right?
21:16 There's other algorithms for
embedded learning like picking
21:21 and exploring various arms.
21:22 Did they try different
ones in this paper?
21:26 The question is UCT is one way
to create this exploitation,
21:30 but there are a
lot of literature,
21:32 now that whether they compared?
21:35 Yeah.
21:36 No, and there is
that whole literature
21:40 of multi-armed
bounded and other ways
21:42 that we can bring in
exploration, exploitation
21:45 into the optimization
process, and all of that
21:47 could be also explored here.
21:51 Their main contribution
is that created a platform
21:55 that now others can
bring in other approaches
21:58 to optimization.
22:01 Yeah.
22:02 Anything else?
22:05 Questions or comments?
22:11 OK, let's move on
to the next paper.
22:15 [INAUDIBLE]
22:17 Yes, go ahead.
22:19 If we want to keep track
of the action trajectory
22:22 based with the Monte
Carlo tree search, what
22:26 if there are times when there's
repeated actions like action AB,
22:29 AB is, or when the same action
is seen in multiple nodes,
22:36 is there any way to
optimize this tree,
22:38 or does this tree recognize
all of these repeated actions
22:43 as independent trajectories?
22:49 So the question is, if a
series of actions are repeated,
22:53 how do you--
22:54 so the philosophy behind this
is that if an action is repeated
22:59 inside a trajectory,
given a parent node,
23:05 you would increase the
count of that action,
23:08 and that comes in
the UCT formulation.
23:11 So ideally, you would
capture in that as you
23:16 are forming this tree.
23:17 And ideally, this is a
tree that you're forming.
23:20 Not some fully
connected graph, so this
23:24 is the assumption behind this.
23:26 Yes.
23:29 So let's now talk about SPRINT.
23:32 This is a NeurIPS 2025 paper, so
this hasn't been even presented
23:36 here at the conference.
23:39 So this paper is about,
again, it gives you
23:43 a flavor of this
planning and parallel
23:48 execution of those
plans and how we
23:50 can use the model itself to
enable it to think better
23:55 in parallel, and we
can optimize that.
23:59 So this paper, SPRINT, was
motivated by this observation
24:04 that the reasoning
models such as o1, Gemini
24:09 Think, Gemini 2.5 Pro, and
pretty much all the frontier
24:14 models right now, they have
this tendency that for harder
24:19 problems, they think more.
24:22 And this longer thinking
corresponds to higher accuracy,
24:26 so these models to think
for longer and longer
24:30 like chain-of-thoughts.
24:32 For example, these
two graphs here
24:34 show that the DeepSeek-R1
during the training process.
24:38 As the training
process continues,
24:41 obviously, it becomes
better at solving
24:43 this, Amy, these math problems.
24:46 But also, if we take a look at
the average length per response,
24:50 that is also going
up, so it seems
24:52 like there is a correlation
between model thinking
24:55 for longer and a
larger sum of number
24:58 of tokens and the accuracy
that we get from that.
25:01 Now, again, so the
observation here
25:04 was that these long
reasoning steps are helpful,
25:11 but at the same time, many
of these reasoning steps
25:14 seem to be independent
of each other.
25:18 For example, the model tries
alternative approaches,
25:22 it decomposes a task into
subtasks that some of them
25:25 can be run in parallel, and
then some of these steps
25:29 are verifying the
previous steps.
25:31 But there is a lot of-- if
we look into the graph that
25:35 describes the
reasoning trace, there
25:40 are parts of these
computations that
25:42 are independent of
each other, so we
25:44 don't need to really wait
for all of these steps
25:47 to be created
sequentially by the model,
25:52 so we want to see how we can
leverage this parallelism
25:56 observation.
25:57 And so the idea is,
we want the model
26:00 identify this parallelization
opportunities and act on it.
26:05 So SPRINT is a
framework that does
26:11 come in during the post-training
and/or fine tuning process,
26:15 and what it does is that
it takes a reasoning model
26:18 and enables the reasoning
model to execute the response
26:24 generation.
26:25 We are a planner that
creates a set of plans
26:32 for how to approach solving a
problem and a set of executors,
26:38 and those executors can be
run in parallel in order
26:42 to carry out the plan.
26:45 And this can happen
again and again.
26:47 We can have the next slide.
26:48 We can have a plan, a
bunch of execution plans
26:55 that are carried
out in parallel,
26:57 and then we can have
another set of plans
26:59 and then another set
of parallel executions,
27:04 so the interleaving of
these planning and execution
27:08 is what it can enable
acceleration of the reasoning
27:12 process.
27:13 So let's see how we can
enable the model to create
27:18 these parallel traces.
27:22 And this is
something that I want
27:24 you to think about it
beyond just this paper,
27:26 and we're seeing it
in the following work
27:28 that we are talking about.
27:30 A lot of times when we want
to create data and figure out
27:37 a certain behavior
in the model, we
27:39 can use the LLMs itself in
the fine tuning data creation
27:44 process, and here is
an example of that.
27:48 Given a reasoning model's
response trajectory
27:54 to a question, we
can decompose it
27:58 in a number of steps via an LLM.
28:00 So in this case, for
example, we had DeepSeek-R1
28:04 generate these reasoning
traces and responses
28:06 to these questions.
28:08 And then we had a
model like GPT-4o
28:11 going through this
reasoning trace,
28:13 and annotate the steps of
the reasoning response.
28:19 And not only that, for
each of these steps,
28:22 we ask the GPT-4o to
annotate whether which
28:28 part is the planning part, and
which part is the execution
28:31 part.
28:32 And in some steps, there were
multiple execution pieces
28:36 for a given plan.
28:40 So for example,
we had this query,
28:43 we had the reasoning
trace, and then
28:45 there are a bunch of things
that needs to be done.
28:47 And then when the reasoning
stops, there is a final answer.
28:52 Then we use GPT-4o to
go through this process
28:56 and create these
steps 1, 2, and k.
29:00 Basically, now we have
these annotations,
29:03 and within each
step, the model also
29:06 annotates the plan
and the execution.
29:09 Which part is the planning part?
29:11 Which part is the
execution of that plan?
29:15 Given that, then we can
create a DAG of these steps.
29:21 So we have step 1 and
step 2 and all the way,
29:23 and we can, again,
use the model.
29:26 And the model does a
really good job here
29:28 of saying whether how these
steps are related to each other.
29:32 For example, step 4 and 2 are
not dependent on each other,
29:36 but they both depend on step
1-- is a follow-up to step 1,
29:40 so now we have a DAG of an
optimizer and basically,
29:45 creating the DAG that describes
how this reasoning trace works.
29:52 And then we can do
packing of these steps.
29:55 For example, step 1
can be done first,
29:58 and step 2 and 3 can be
done completely in parallel
30:01 with each other and so on.
30:03 And once we have these data
set that we have annotated,
30:12 then LRM here is just a
large reasoning model.
30:14 Basically, all LLMs are now
inherently reasoning models,
30:19 so what we are creating
here is this data set
30:22 of the steps, plan, and
executions in parallel,
30:26 and we basically fine tune
the model, for example,
30:30 DeepSeek-R1 to now
think in that way.
30:33 So previously, we would
just create those inherently
30:40 have these
properties, but now we
30:42 want the model to think
more and more in parallel
30:44 by showing these parallel-like
planning and execution traces.
30:49 And we just fine tune the model.
30:50 In this case, just a
supervised fine tuning
30:52 of basically showing the
model the same stuff,
30:56 the same thinking processes, but
now annotated with these texts.
31:03 And this helps the model
that at inference time, now,
31:06 the model can output these tags.
31:10 For example, here
is plan 1, and then
31:13 here are the execution
patterns for this.
31:17 And here is plan 2, and so on.
31:20 So, for example,
for plan i, there
31:22 is a set of thinking
and a parallel execution
31:25 that the model just
outputs itself,
31:27 and then we can
go over executing
31:31 these plans in parallel,
and then syncing the output
31:35 and returning the context.
31:36 And then the model goes
through plan i plus 1,
31:40 and then there is a number
of parallel subplans
31:45 within that the model can
output and we can go from there.
31:53 Why this matters?
31:56 So the cost of LLM
inference, especially when
32:00 we get to multi-step reasoning,
becomes a huge burden.
32:04 And you might have already
noticed that yourself,
32:07 and you spend a lot of time
waiting for the model to output
32:10 the response it gets.
32:15 It might make you not happy,
you want the answers fast,
32:18 but also it's a lot of costs
and a lot of delay that
32:21 goes into generating
these responses.
32:24 So right now, here is how
the sequential reasoning
32:27 models work, so there is
a query, there is a plan,
32:31 and then execution of that plan.
32:33 There's plan 2, execution
of plan 2, and so on,
32:36 so this is the
time that it takes
32:38 to generate, or go over
this thinking process
32:42 and generate the final answer.
32:44 But if we could leverage
this independence
32:48 from plan 1 and plan 2, we
could have the model execute.
32:57 We could have the
execution of those plans
32:59 be done at the same time.
33:03 Here is what after we
fine tuned with the spring
33:06 at inference time happens, so
instead of model generating
33:09 plan 1 and executing that,
then generating plan 2,
33:13 model generates these two
plans first, plan 1 and 2,
33:19 and then it starts executing.
33:21 The execution of those plans
happen at the same time.
33:24 And then the execution
could be using a tool.
33:27 For example, the model is
come up with a calculation,
33:30 and then we can use
this calculator Python
33:33 to execute plan 1 and
plan 2 and so on and then
33:37 go to the next stage.
33:39 And the fine tuning
data, again, this
33:42 is another visualization of how
given these annotations that we
33:47 have for plans and execution,
we create the fine tuning data,
33:51 so we are basically
asking the model
33:53 to think in parallel,
if the plans are
33:56 independent of each other.
33:57 We are basically teaching the
model to come up with plan
34:00 1 and 2 at the same
time, because they're
34:02 independent depend of each
other and we execute them.
34:05 Yes.
34:06 So if there's a need
for a replaning,
34:09 how does the model
remember which
34:12 plans correspond to
which executions, and all
34:15 of those things?
34:18 Later in the infant stage,
after the execution for someone
34:23 who realizes that, oh,
what I did was wrong.
34:25 How does it remember to
do a replanning of go
34:29 to the plan of 3
instead of plan of 2?
34:37 So this fork, you're bringing
the previous work in here.
34:42 Here, the model can-- so what
we are teaching the model
34:45 here is that to think about
plans at each point of time,
34:51 even if it's a revision
of an existing plan.
34:57 If it can generate plans that
can be executed in parallel,
35:03 it should do so.
35:04 It should not wait for
the execution of plan 1
35:07 to generate plan 2, because
plan 2 is independent of plan 1
35:12 anyway.
35:13 So this is how we are
creating this data set
35:16 for training the
model to teaching
35:19 it to think
maximally in parallel
35:21 and generate those plans.
35:23 If the model wants to go
back and reverse on a plan,
35:26 it still can do that.
35:27 It still sees all
of these contexts.
35:30 It's just like the model
is trained to think more
35:33 in parallel.
35:34 And also because it's
trained to be like that,
35:36 and we have this special tags,
or ways of the model generating
35:41 these plans and
execution plans, we
35:43 can act on it and leverage
those parallelism.
35:48 Yes.
35:49 Is the plan to change the
structure of this LLM,
35:52 because before, you just need
to predict the next token,
35:55 but now you seem to have
three parallel lines?
35:59 It's always next open.
36:01 It's just that there is
instead of everything, the plan
36:05 and execution, one at a time,
if there is a tag like here,
36:09 this is plan i, and
here are the execution.
36:13 And here is plan 2,
plan i and i plus 1.
36:17 For example, here is
plan 1 and plan plus 2.
36:19 This is the high level count.
36:20 And then now that we know that
there are these two plans,
36:23 we can just branch out
and run them in parallel.
36:26 So that's the idea here.
36:30 So here is the training
recipe starting from--
36:34 so we generate 6k thinking
trajectories for MATH data set.
36:41 We keep the ones with
higher parallelization,
36:45 and we do supervised fine tuning
on DeepSeek-R1 Distill-Qwen-7B
36:52 on this reformatted
trajectories.
36:55 And the interesting
property that we observed
36:58 was that, so when we
started the project,
37:02 the goal was to
maximize parallelism
37:05 for reducing the sequential
token generation,
37:10 so we save on that.
37:11 But it turns out this process
actually helps out with accuracy
37:15 as well.
37:15 The model seems to like these
more structured way of thinking,
37:20 and this way of
encouraging parallelism
37:24 helps the model have
higher accuracy as well.
37:27 And here, what we are showing
that is the average number
37:29 of sequential tokens over
the baseline model like R1
37:34 Distill-7B.
37:36 And the SPRINT model,
again, is distilling R1.
37:39 This basically, there we are
fine tuning the 7B model,
37:43 and there's a big jump like
a 3 and 1/2% jump over that,
37:49 while also becoming much more
efficient than a 32B in terms
37:54 of number of sequential tokens.
37:59 Like you said, there's
[INAUDIBLE] and more opportunity
38:03 to explore more approaches
given the fixed compute budget,
38:08 because--
38:08 It could be, yeah.
38:10 And we have some
data on that, which
38:12 I believe I'm going to show.
38:14 The model does explore more
and think in parallel more.
38:20 And another
interesting observation
38:22 was that we have out of
domain generalization as well.
38:30 So the training to
think in parallel
38:37 was done for the MATH
data set, but we also
38:40 saw the model is doing better.
38:42 Not only have more opportunities
for this parallelism, but also
38:48 higher accuracy, for example,
countdown or GPQA diamond data
38:54 set, so there is no training.
38:57 We have not trained
on those data sets,
38:59 but the model generalizes.
39:00 And this could go back to
what you were suggesting,
39:03 that the model can
think in parallel.
39:05 And that inherently
seems to help the model,
39:09 but as a side effect, we
also have opportunities
39:13 for leveraging this parallelism
and reducing the number
39:16 of sequential tokens.
39:20 Could there be a scenario, where
individually, the answers are
39:24 correct in parallel branches,
but when you combine it,
39:29 say in a sequential manner,
the answer may be wrong,
39:32 and in that case, what
will take precedence?
39:35 And in that case--
39:37 What will take precedence?
39:38 Because sometimes, even in
a mathematical equation,
39:41 individually, when you
look at them in isolation,
39:44 the answer might look
seemingly correct,
39:46 but when you put all
the steps together,
39:49 the answer may
eventually be wrong.
39:53 So when the model
generates, no matter
39:57 if it generates
sequentially, or in parallel,
40:00 at the end of the
day, everything
40:02 is condensed into the context,
so the model sees that.
40:06 And this is the
thinking process.
40:08 The answer, after
this, the model
40:11 should generate a
synthesized final answer,
40:14 so if there are contradictions
in the sequential,
40:17 or in parallel, the
model is expected
40:20 to resolve that before
generating a final answer.
40:23 So in that case, it's
a little difficult
40:26 to say because both approaches
can suffer from contradictions
40:32 in the thinking.
40:33 But here, what we are seeing is
more that these plans are rather
40:40 than being different approaches
to solve the same problem,
40:42 they're different steps
to solve one problem.
40:48 So another interesting
observation was that--
40:55 and perhaps intuitive
some that harder problems
40:59 require more iterative
planning and execution.
41:04 The other observation-- this was
maybe less intuitive was that
41:07 in the early stages--
41:10 so we have a bunch of these
parallel planning execution,
41:13 parallel planning execution.
41:15 In the early stages, the more
parallelism, or more exploration
41:21 is observed by the model,
and then in the later stages,
41:25 we converge to
maybe to less plans.
41:35 Basically, the exploration
is more in the early stages,
41:39 and towards the end, we
want to really go dive deep
41:42 into a single plan
and execution.
41:44 Yes.
41:46 How can you ensure that
the independent reasoning
41:48 tasks are evenly load
balanced and do not
41:51 encounter bottlenecks?
41:54 Do independent
tasks, for example,
41:56 have similar expected
execution times?
42:00 Here, you are saying
that how do we make sure?
42:04 So when we divide
independent tasks,
42:07 how do we ensure that these
are going to be executed
42:10 in about similar times?
42:13 So the question is,
how do we ensure
42:15 that these
independent plans that
42:17 are now run at the same time,
they take similar times?
42:23 So the thing is we
can ensure that.
42:27 There are some measures
taken to enable that,
42:30 but we still could
have a straggler.
42:32 Maybe step 2 versus
4 here, step 4
42:34 may take a lot longer than
step 2, but at the same time,
42:39 we are confined to just step 4,
not step 4 plus step 2 runtime.
42:46 And we have some measures.
42:47 For example, if the
execution is just too simple,
42:53 we merge that into
the plan and try
42:55 to create these bigger
and bigger chunks
42:57 that we can do in parallel, but
that could be an optimization
43:02 as well, the optimizing
this across the stages.
43:07 So I was wondering
if there's a group
43:10 analysis for it [INAUDIBLE]?
43:12 I'm not sure.
43:13 I'm not sure if there's
analysis exactly on that.
43:18 Question?
43:19 Yes.
43:20 Could you go back to the slide?
43:22 So I saw on the MATH
and GPQA, the SPRINT
43:26 has comparable
accuracy and number
43:28 of tokens as the baseline.
43:31 So I'm curious, for
those benchmarks,
43:35 what is the mean
width of the tree,
43:39 and what's the maximum width?
43:45 In terms of because
the width of the tree
43:48 determines how much
parallelism you can exploit.
43:52 So what you're getting
at is that the width is
43:56 task-dependent, basically?
43:57 Yeah.
43:58 The parallelism that we can
exploit, and for some of these,
44:02 basically if the ratio
of the sequential tokens
44:05 is for one task.
44:09 For example, I believe, for MATH
is lower than for GPQ domain,
44:15 then yes, that's an
indication of parallelism.
44:18 Some tasks could be inherently
more parallel than the other.
44:22 And I don't know the exact
number of the width of the tree
44:24 here, but that to be able
to leverage this approach,
44:29 parallelism should exist.
44:31 But what we observed
is that that
44:34 is the case for many of the
reasoning problems like MATH
44:37 and other reasoning
tasks in GPQA and so on.
44:41 And some of these are--
44:45 again, for example, if you look
at this for the MATH data set
44:50 compared to some of
these methods with even
44:56 lower, but comparable accuracy,
we are increasing the bandwidth,
45:01 or reducing the number
of sequence token
45:05 by something like 40%, which
is a long, large number.
45:12 But it is true that this is
going to be task-dependent.
45:19 And maybe getting back
to your questions,
45:22 we have larger
savings for problems
45:25 that need more thinking.
45:27 So for example,
here we are showing
45:30 the sequential token reduction
by SPRINT over the baseline.
45:35 Sorry, over the RFT model.
45:38 This is the rejection
fine tuning methods,
45:40 so this is a baseline
we are comparing with.
45:45 If the number of tokens in
generated, like in the thinking
45:51 process is small, then there
is probably less opportunity
45:56 for parallelism.
45:57 So by doing this, oh, let's
plan and execute, actually,
46:02 we can be worse
than the baseline.
46:05 But this appears in the
harder problems and problems
46:08 that require more thinking and
more number of parallel tokens,
46:13 and that's where this method
shines and shows in parallelism.
46:17 I'm not sure how many of you
have read the recent Sonnet 4.5
46:22 system card, but it was very
interesting to me that it says,
46:26 the prompt for the
system card encourages
46:30 the model to use tools as much
as possible, and, at least,
46:34 100 times.
46:35 That's a very large
number that the model
46:38 is encouraged to use the tool.
46:40 And this just shows that we are
going into this regime that we
46:46 are solving more and more
interesting problems,
46:48 and we are actually going
more and way beyond 8 to 10k,
46:51 even for the number of tokens
that the model deals with
46:55 for solving a problem.
47:00 Yes.
47:02 So can you come back to the
fine tuning of data set diagram
47:07 with all the trees?
47:10 Fine tuning process.
47:13 I think one.
47:14 Yeah, there.
47:15 Doing inference, does it
reduce the entire step 1
47:21 to step k the entire thing,
but different layers,
47:24 or does it do a sequential?
47:25 No.
47:25 During inference,
it just likes this.
47:29 So the model learns
to generate plans
47:31 that can be executed in
parallel at the same time,
47:36 so it first generates
plan 1 and 2,
47:40 and then once plan 1 is
outputted, execution of plan 1
47:45 starts.
47:47 Once plan 2 is outputted,
execution of plan 2
47:50 starts, then the result is
put back in the context,
47:54 and then the model is
generating two more plans.
47:58 So the model still takes
this sequential approach
48:01 to generating plans
and execution,
48:03 but the difference is that
if it learns, or is trained
48:08 to at each point of time,
if there are plans that
48:12 can be executed in
parallel, it generates
48:15 those at the same time.
48:16 So here, would be
after step 1, it
48:20 generates step 2 and
4 at the same time,
48:22 and then you see the results
for that and then so on
48:26 and it continues.
48:31 So think about it, each
step is a plan and a set
48:34 of executions in the training.
48:42 But this step here is
defined as plan 1 and exit 1,
48:46 and then it be changed
the notion of--
48:52 Do they also match this?
48:55 So let's say, they execute two
plans that can be parallelized,
48:59 and then they
collect the context
49:02 and then add it to the
prompt for the next level.
49:06 Do they also do that
in the training phase
49:09 as well to match how
they are proping it?
49:13 This is how the training
data will look like.
49:17 So plan 1 and 2 are
independent, so plan 1 and 2
49:21 are put together
next to each other,
49:23 and then we have execution
1 and 2 during training.
49:26 So that's how the model
sees during training
49:32 that plan 1 and 2 could
be outfitted together,
49:36 but at inference, the
execution is actually
49:38 also done in parallel.
49:42 Let's move on to the
last paper because I want
49:46 to make sure we cover that.
49:47 But just before
that, opportunity.
49:50 So here, the work that
supervised fine tuning,
49:53 but, of course, methods like RL
and GRPO can enable potentially
49:58 much more benefit from
this data and much
50:01 more this
generalization property
50:03 usually works well with RL.
50:10 And other notions about
tool use, overlapping
50:15 different tools, or actually
realizing the wall clock speed
50:20 of this other work
that can be done here
50:22 in the implementation
of this method.
50:25 So now, let's go through
another method called SWiRL.
50:29 This is also a continuation
of multi-step synthetic data
50:35 generation and helping the
model do multi-step better.
50:41 And this is a work that
is going to be presented
50:43 next week at COLM in
Conference in Language
50:46 Modeling in Montreal.
50:48 So this is another
just a preview.
50:51 This is another training.
50:53 We are using training
and basically
50:55 fine tuning a language
model to help it
50:57 do multi-step reasoning better.
51:00 So motivation, again,
many real world tasks
51:03 require multi-step
reasoning and tool use.
51:05 For example, if you want to
answer multi-hop question using
51:09 a search engine, you want
to solve math problems,
51:12 or use solving a software
engineering like doing
51:16 a project, planning a trip,
analyzing data, and so on.
51:19 Usually, we go as humans,
we use these tools,
51:23 and reason through them for
important tasks more than one,
51:27 so we need a cohesive number
of steps of reasoning and tool
51:31 use in order to solve a problem.
51:35 So the challenges, again, in
multi-step reasoning and tool
51:38 use setting is that then you're
doing reasoning and tool use.
51:45 Even for one step, it
can get complicated,
51:48 but as we expand on
this and generate
51:52 multiple steps of
reasoning and tool use,
51:54 the errors and the
complications can compound
51:57 over these different steps.
52:01 If we want the model to-- and
another focus of this paper
52:05 is enabling tool use,
like teaching the model
52:08 to use the right tools,
for example, a calculator,
52:11 Python executor, and so on.
52:13 Using these tools live
during the training process
52:17 can be very challenging
because tools can fail,
52:21 they can be slow, and the
training process is already
52:24 time consuming and challenging,
so this can further
52:28 slow that down.
52:31 And if you look back in terms
of the fine tuning processes,
52:35 such as reinforcement
learning from human feedback,
52:38 from AI feedback, or execution
feedback, many of these
52:46 are optimized for
single step tasks.
52:48 Basically, the model takes a
lot of whatever it wants to do,
52:52 generates a final
answer, and the reward
52:55 is just based on the final
answer, whether it's correct
52:58 or not, and then we back
propagate that towards actions.
53:02 And here, we want to
have more of governance
53:10 on the process of
generating these steps
53:13 and how we can optimize them.
53:15 So this framework called SWiRL,
and the design goal for SWiRL
53:23 is the following.
53:24 First of all, at
a high level, we
53:27 want the model to solve complex
problem and multi-step reasoning
53:31 task.
53:32 We want the model to
know when to call a tool,
53:36 generate the right
queries to invoke a tool,
53:39 because we need to
know how to use a tool,
53:42 the model needs to know that,
carry out these reasoning steps
53:47 and maintain
accuracy across them,
53:51 and learn how to
recover from an error
53:54 and learn when to stop taking
new steps and calling new tools,
53:59 and say, OK, I'm now ready
to generate a final answer,
54:03 so we want the model
to know these steps.
54:06 We also want to avoid using
tools during the training
54:10 process, because like I
mentioned, this can be slow.
54:15 Tools can fail, and can have
bugs, so we want to avoid that.
54:20 And ideally, we want the
model to generalize this,
54:23 so ideally, we want
the model to learn
54:26 when to adapt to new tools
and new reasoning tasks
54:31 and capabilities.
54:34 So to approach this,
here is the process.
54:40 The first step of this process
is that let's start with
54:48 creating synthetic
multi-step data for a model,
54:52 so given a prompt--
54:54 and in order to really
annotate these steps,
54:58 let's have the model
take one step at a time
55:04 and let the model know at each
step that it's free to reason,
55:09 create a chain of
thought, call a tool,
55:13 or propose a final answer.
55:15 So having an input prompt at
step 1, we tell the model,
55:21 you have access to
these tools, you
55:24 can generate a reasoning step.
55:26 If you're ready to
generate the final answer,
55:29 just say that and create that.
55:31 So given this prompt, the model
would take the first action,
55:37 which could be a reasoning
step followed by a tool call,
55:41 and then we show the model
the environment response.
55:49 So given that, then we show the
model again the same prompt,
55:55 but this time, we have the
context from the previous step.
55:59 So basically, we say, here
is the original prompt,
56:03 here is the previous
action, and here is
56:05 the result of taking that
action from the environment.
56:08 You can take a new
action and call
56:12 a tool, or if you're ready to
create a final answer, just
56:17 output the final answer.
56:19 So by design, through this
adapt to iterative prompting,
56:25 we are creating this
multi-step data set,
56:27 and the steps can
be from 1 to 3 or 5,
56:31 and so on for different queries.
56:37 Then we need a label.
56:40 We want to have a notation
of how good this step is,
56:47 and to do so, we ask
an LLM-as-a-Judge,
56:51 given the prior context
and the current action,
56:55 which is a reasoning step,
followed by a tool called,
56:58 give us a reward function, or
give us your estimate of how
57:02 good this trajectory
and final action is.
57:10 Given that we have for each
query and we have a set
57:14 of steps, and for each step, we
have a LLM-as-a-Judge score that
57:20 is assigned to that step.
57:22 And we can do that offline.
57:24 We can go through many, many
questions in parallel offline
57:27 and generate these steps
and labeled annotations.
57:33 Once we have these
steps per prompt,
57:37 we can filter this
data in different ways.
57:39 For example, we can
only keep the data,
57:43 where the LLM-as-a-Judge decided
every single step was a good
57:50 step.
57:51 Every single action was good.
57:53 Or we can go based on
outcome filter data,
57:56 and that would be we
keep all the trajectories
58:00 that the final answer was
correct, no matter what
58:03 the label per step was.
58:04 And we're going to see how these
two differed with each other.
58:08 But the whole intuition,
motivation behind this part
58:14 is that, for these
reasoning prompts, we
58:17 have a number of steps,
and then for each step,
58:24 we have a reward created by
the model, which we can use
58:27 or not use during our
training, but let's
58:30 see how these two play out.
58:32 Then having this data that
we have generated offline,
58:37 we can start the
training process,
58:40 and the training in
this part is done based
58:42 on reinforcement learning.
58:44 So maybe you can pay attention
to this figure on the right.
58:47 This is a very simple example,
but let's go through that.
58:50 Who is older, Glenn, I
don't know the last name,
58:54 or Ross Lynch?
58:55 So these two people,
who is older?
58:57 So action 1 is to
figure out who is older.
59:01 I should first search for
age of the first person.
59:07 Then we have a reward
for this action.
59:09 We ask the judge, LLM-as-a-Judge
to say given an input prompt
59:13 and this action, what is
the reward for this step?
59:21 Then we actually go and show the
model the result of this step.
59:29 This is already we have
in our training data,
59:31 so we have the
environment response,
59:34 and then we prompt the model
to take the next action.
59:37 And then the next action
is this second question,
59:39 which is about the age
of the second person.
59:42 We have a reward based on that.
59:44 And at the last stage
we say, given the result
59:49 of the previous searches,
we asked the model
59:52 to generate another action.
59:55 In this case, the
model seems to be
59:56 ready to output
the final answer,
59:59 so it outputs the answer
in these tags answer
1:00:03 and the final answer
is there, and we
1:00:08 can get a reward based on that.
1:00:11 So the point that I want
you to pay attention to
1:00:13 is how we manage to not have
the tool calls during training.
1:00:18 So basically, what
we are doing here
1:00:20 is that we have this
trajectory from the prompt
1:00:24 and from these pre-collected
actions and tool calls.
1:00:34 During RL process,
we get the reward.
1:00:38 We show the prompt and steps
and actions onto that action k,
1:00:44 in this case, for example, up
to action 1 and the environment
1:00:48 response, and then we ask the
model to take the next step.
1:00:52 So this is the part that
is done during training.
1:00:54 The model takes the
next action, but we
1:00:58 don't need to execute that
action or call the tool.
1:01:02 We just collect the reward
based on that specific action
1:01:08 and use that for
RL optimization.
1:01:11 All the tool calls are just
done during the data annotation
1:01:15 process outside of the
RL fine tuning part.
1:01:18 Because we realize that the
LLM just does a good job based
1:01:23 on the quality of the
action that's proposed,
1:01:27 we're good in just
evaluating that.
1:01:29 We don't need to execute the
action and evaluate that.
1:01:33 So that's how we
separated the two.
1:01:36 Do you need to train LLM
Judge with this for use?
1:01:42 So we did not train an
LLM-as-a-Judge for this.
1:01:46 We just prompted--
1:01:48 I'll talk about what models
we used for each one, so there
1:01:53 was no training for that.
1:01:55 But if you the judge cannot see
the real output from the tool
1:02:01 use, how do you [INAUDIBLE]?
1:02:07 So the question is if the
judge cannot see the output
1:02:11 of the tool, how can it
give a reasonable score?
1:02:14 So here's the point here.
1:02:16 So we are asking
the judge to judge
1:02:20 the quality of the query that
is generated by the model
1:02:25 to call the tool, rather
than the output of the tool.
1:02:28 Like here, what the judge
sees is that the model
1:02:31 is asking age of this person.
1:02:35 And the model can judge
that this is a good question
1:02:39 to create for the search
engine before seeing
1:02:44 the result of the search engine.
1:02:45 The model doesn't need to know
the age of this person to know
1:02:48 this question was good or bad.
1:02:50 This is a good question.
1:02:51 This is a reasonable question.
1:02:59 So basically, what we are
doing is providing this process
1:03:03 feedback, process
reward for this step,
1:03:06 and the tool calls are
captured in the prior context.
1:03:09 So all of these
tool call resources,
1:03:12 we have collected them in our
offline training data set.
1:03:15 We are not doing that during
the actual RL fine tuning.
1:03:21 So to just show you the
objective function that
1:03:25 is being optimized in
this multi-step RL is,
1:03:30 let's say we have a number
of steps S1 to SK, and then
1:03:35 for each followed by an
action, which is a reasoning
1:03:38 step followed by a tool call.
1:03:40 What we are doing
here is that we
1:03:42 are optimizing the expected
reward of a single action, given
1:03:48 all the context so far, which
is a set of states and actions
1:03:52 that we have collected also.
1:04:00 So that's how we are
optimizing the expected reward
1:04:04 of a single action in
a multi-step process,
1:04:07 given all the prior
steps, but, of course,
1:04:11 this varies from action 1
all the way to action K.
1:04:18 Now, during inference
once we RL this model,
1:04:24 let's walk through
an inference process
1:04:26 of how we encourage the model
to do this multi-step process.
1:04:29 So, for example,
here the prompt is
1:04:33 help me answer the following
questions in just a few words.
1:04:39 And then we specify the
tool that the model can use,
1:04:42 in this case, a calculator.
1:04:44 If you think it would
help to use a calculator,
1:04:46 please generate a
mathematical query
1:04:49 enclosed by these kind of tags.
1:04:55 And then we also tell
the model, once you
1:04:59 have enough information, you
can generate an answer tag
1:05:03 and generate the final answer.
1:05:05 So through these tags, the
model can tell us the tool call,
1:05:10 or if it's ready to
generate the final answer.
1:05:13 So here is the input question.
1:05:17 So in step 1, the
model is prompted.
1:05:20 Here is the input question,
the model responses
1:05:25 to that question.
1:05:27 And in this response is
calling it the calculator,
1:05:30 and it's calling this is the
math that it wants to run.
1:05:35 The user provides that output.
1:05:38 Basically, that tool is
executed with that given input.
1:05:42 We give the output to the
model, and then the model
1:05:45 is prompted again.
1:05:47 Again, here is the input.
1:05:49 Here is the result from the
previous thinking process
1:05:54 and tool call, and the
model takes the next action,
1:05:58 and next action and so far.
1:06:02 So we are iteratively
prompt the model.
1:06:04 Here is what happens so far.
1:06:05 Here is the tool you have.
1:06:06 If you're ready to generate
the final answer, do it.
1:06:09 If not, continue using the tool.
1:06:16 So the experimental setup for
this approach was the following.
1:06:19 There is a model Gemma-2-27b
was used to create
1:06:26 this multi-step synthetic data.
1:06:28 The questions were coming
from HotPotQA and GSM8k.
1:06:34 We had something like
50k sourced from a number
1:06:39 of problems and created for
different kinds of data that
1:06:44 were, like I said, we can
process this data that we
1:06:47 created based on process filter,
outcome filtered both process,
1:06:53 and outcome filtered or random.
1:06:55 And then we also collected a
number of trajectories, I think.
1:07:00 So let's take a look at
impact of data filtering
1:07:04 on the performance of SWiRL.
1:07:07 One perhaps in the beginning,
this was non-intuitive,
1:07:11 but we realized why
this is happening
1:07:14 is that it seems like when our
training data was only processed
1:07:19 filtered, meaning we
took reasoning steps that
1:07:23 were majority like voted
yes by LLM as a Judge
1:07:29 from the reasoning
steps, but we like
1:07:31 didn't filter them based on the
correctness of final answer.
1:07:35 This seems to help the training
more than if we rigorously
1:07:44 only took trajectories where
the outcome was correct,
1:07:48 or both process and
outcome were correct.
1:07:51 And the reason for that is
if we only get trajectories,
1:07:55 where the model already knows
the outcome and is correct,
1:07:59 perhaps you're not helping
the model solve problems
1:08:02 that it couldn't solve
during test time,
1:08:04 because we are training
it to think differently
1:08:07 about these problems, so
it can solve new problems
1:08:10 that it couldn't solve before,
but it had gotten the sum
1:08:14 processes correctly.
1:08:19 But perhaps the
most interesting,
1:08:21 and this is, again,
something that we
1:08:23 are seeing in the
SPRINT project as well,
1:08:26 is the generalization
performance of the model.
1:08:29 So for example, we
had SWiRL on GSM8k.
1:08:34 These are MATH problems, and
we were teaching the model
1:08:36 to use SymPy, a
calculator basically,
1:08:40 to solve these problems.
1:08:42 So that was the training data.
1:08:44 And then once we do this
multi-step optimization using
1:08:50 GSM8k, we then
tested on HotPotQA.
1:08:54 And this is the
accuracy that increase
1:08:57 that we get from the base
model, so it goes from 65 to 71.
1:09:03 And if we were to use exactly
HotPotQA, and in this case,
1:09:07 the tool for HotPotQA was a
search tool, not a calculator,
1:09:14 the increase was from 65 to 73.
1:09:17 So and vice versa,
this was true as well.
1:09:20 If we train the model on
HotPotQA with a search tool,
1:09:23 it could also do well
on GSM8k with Python.
1:09:27 So it seems like there is
something going beyond just
1:09:30 like learning to use a
specific tool, rather,
1:09:34 the model is learning
how to think in steps
1:09:37 and how to learn how
to invoke a tool.
1:09:43 And these data sets,
the other data sets
1:09:45 are separate from any
of our training data.
1:09:51 Another important observation
here was that, again,
1:09:55 in this case, the model is
being trained on HotPotQA
1:10:01 using a search tool
for all of these,
1:10:04 but we are showing
the test results
1:10:07 as we are increasing the
synthetic data, the training
1:10:10 data size.
1:10:11 So it seems like as we go from
100 training examples to 10,000
1:10:16 training examples,
even at inference,
1:10:19 the model is improving on a
completely different task,
1:10:22 which is MATH
problems and GSM8k.
1:10:25 So this is, again, it's the most
important graph from this paper
1:10:31 showing that by creating
synthetic data in environments
1:10:36 that are perhaps easier
to create these data for,
1:10:41 and teaching the model
how to use these tools
1:10:44 and how to do things
in multiple steps,
1:10:48 we can generalize these
behavior to entirely new tools
1:10:52 and domains.
1:10:53 And perhaps, scaling
this up could
1:10:55 be a very powerful methodology.
1:11:05 And here, we are
showing some results
1:11:11 to try to interpret why the
model is becoming better
1:11:17 in through this RL processes.
1:11:20 And what we did here is to
look into the average process
1:11:24 reward per step of
the model in answering
1:11:28 these questions before
and after being fine
1:11:31 tuned through this
reinforcement learning process.
1:11:36 And perhaps this is,
again, very intuitive
1:11:38 that the process
correctness of the model
1:11:41 has improved
throughout this process
1:11:44 for both in-distribution
domain, where
1:11:47 we train on HotPotQA,
and out of distribution
1:11:50 when we just tested on GSM8k.
1:11:52 So the model thinks more
correctly per step, both for
1:11:58 on the training data, but
out of distribution data.
1:12:02 And here are some other
results that we also
1:12:07 looked into precision,
recall, and other metrics
1:12:10 across a number of tasks.
1:12:15 And here are how this works
compared to frontier models.
1:12:23 Something that perhaps
is worth noting here
1:12:29 is that we could do all of this.
1:12:32 That all of this process
that we did with RL,
1:12:35 we could do it with supervised
fine tuning as well,
1:12:39 and it turns out that this
multi-step RL does better
1:12:43 by a good amount over
supervised fine tuning.
1:12:47 And especially for
supervised fine tuning,
1:12:50 it seems like the
model really benefited,
1:12:53 like the training data
needed to be correct,
1:12:55 both process and
outcome filtered.
1:12:59 Supervised finding on
that kind of training data
1:13:02 worked better than
when we selected
1:13:06 only the process filtered data.
1:13:09 And it makes sense because
in supervised fine tuning,
1:13:13 it's an imitation learning.
1:13:16 We are showing these
are the trajectories,
1:13:18 and we want the model to
repeat those in a way.
1:13:21 And then if they're
incorrect, the outcome
1:13:23 is incorrect, it might
hurt performance,
1:13:26 whereas in RL, we are giving
the model a new chance
1:13:30 to take a new action
within the prior steps.
1:13:34 And we are giving a reward
based on that new action,
1:13:37 and that's how it can
break out from this.
1:13:41 And here are some other results,
but because we are out of time,
1:13:48 let's just take a look
at the summary of this.
1:13:51 So again, a
important observation
1:13:54 was that soil of generalizes
across data sets and tools.
1:13:59 It transfers to disparate task,
and the model learns better
1:14:04 from process filtered data,
and it can get a lot of gains
1:14:09 from more synthetic data, both
for in domain and out of domain.
1:14:14 And from just understanding
why this happens,
1:14:18 it turns out that
after this fine tuning,
1:14:23 the process correctness
of the model
1:14:25 improves, so if we just
go to evaluate that,
1:14:28 the model becomes better at
this multi-step thinking.
1:14:33 Again, this is true for
both in-distribution and out
1:14:36 of distribution data.
1:14:38 And with that, we can
conclude this lecture.
1:14:42 I hope you learned more about
multi-step and reasoning
1:14:46 and planning, which is
a very active field that
1:14:48 is going forward.