3 ms·

I don't get why you need tree search at all? What does it give you over a pure LLM trained to do CoT in a tree-like manner? If the context window's long enough

I don't get why you need tree search at all? What does it give you over a pure LLM trained to do CoT in a tree-like manner? If the context window's long enough, it can generate the reasoning-tree just by pure next-token prediction, and rather than BFS, it can guide the tree search with its own value function (which is part of the LLM itself) instead of sticking to hard algos like BFS and DFS. By the way, BFS sounds like it will give you thorough results, at the cost of increased compute. Useful for beating benchmarks, but probably causes marginal improvement for massively improved compute. Still, the improved quality could be meaningful, if it's used for generating training data for Llama4

dietr1ch 2y ago
Tree search is natural when you want a path to navigate, so it does fit a sequence of interactions in a conversation too. I agree that both, DFS and BFS are likely awful[^0], but a more informed approach can probably do better[^1]. Also, at some point on generating the conversation/reasoning tree through token-prediction you need to choose which of the possible conversations you are going to keep on extending/generating, which maps precisely to choosing which node in tree search to expand. I'd argue instead that everything has to look like a search algorithm from, at least it'll be the case for anyone who has studied it more deeply. I'll go even further and claim that Tree Search is Complete as for every problem there's a solution space that can be navigated with a Tree Search Algorithm[^2]. I used to think that you could walk down the space of provable things, but now in the LLM hype days it seems you only need to walk the space of conversations that you can generate. --- [^0] with DFS always at risk of giving obnoxiously long answers, or not terminating if there's loop or spirals [^1] probably through metadata coming from latent variables meaningful to judge a conversation (certainty, ~branching size of a reasonable conversation, whether there's open questions left) [^2] Even if that was poorly done like on combinatorial problems. Imagine a sudoku where you only check the rules once you fill all cells.

dietr1ch 2y ago

Tree search is natural when you want a path to navigate, so it does fit a sequence of interactions in a conversation too. I agree that both, DFS and BFS are likely awful[^0], but a more informed approach can probably do better[^1]. Also, at some point on generating the conversation/reasoning tree through token-prediction you need to choose which of the possible conversations you are going to keep on extending/generating, which maps precisely to choosing which node in tree search to expand. I'd argue instead that everything has to look like a search algorithm from, at least it'll be the case for anyone who has studied it more deeply. I'll go even further and claim that Tree Search is Complete as for every problem there's a solution space that can be navigated with a Tree Search Algorithm[^2]. I used to think that you could walk down the space of provable things, but now in the LLM hype days it seems you only need to walk the space of conversations that you can generate. --- [^0] with DFS always at risk of giving obnoxiously long answers, or not terminating if there's loop or spirals [^1] probably through metadata coming from latent variables meaningful to judge a conversation (certainty, ~branching size of a reasonable conversation, whether there's open questions left) [^2] Even if that was poorly done like on combinatorial problems. Imagine a sudoku where you only check the rules once you fill all cells.