What kind of search does R1 do?

[ajyl]

Research Question

Can we characterize what kind of search reasoning models do? BFS, DFS, hill-climb, other?
Can we find the mechanism of its search procedure? For instance, does it have some preference over some branches over others?

Owners

Andrew Lee (@ajyl)

Project Status

Work in Progress

[wattenberg]

Is this related to the question of finding backtracking? #6

[firstuserhere]

My thoughts on the few examples you gave for searches:

• It's not BFS - Reasoning models aren't generating all possible paths - the initial bit of finetuning/SFT already gives them a structure to start from. You could call consensus@64 a weak form of BFS but i think that doesn't really count.

• It's not DFS - that would involve backtracking whereas models are learning heuristics via rewards. Even a COT backtracking isn't really backtracking, it's still linear.

I'd characterize it as a guided greedy search to have an initial hypothesis. Now, to find the mechanism, I'd first find the heads that are focused on retrieval, some heads that are focused on self-consistency etc and go from there.