4 ms·

Interesting. Due to its emphasiss on BFS, it's the opposite of something I've been trying (I named it the "Tree of failures"). My assumption was that humans do

by jeswin 2y ago

Interesting. Due to its emphasiss on BFS, it's the opposite of something I've been trying (I named it the "Tree of failures"). My assumption was that humans don't try a breadth-first approach. Instead, we split a task into a short-step (instinct and intuition selected), and long-step that summarizes/stores the next steps. The key idea is to recursively evaluate a task as a short-step (high-res - gets executed) and a long-step (lower-res - is just stored), until it succeeds or fails. If it fails, we must walk back keeping a summarized tree of failures in state so that we can exclude them in future selections. The effectiveness of instinct has a steep fall-off at longer distances - so it's better not to chart out of a series of steps. When we do BFS, we drive down the value of instinct in favor of compute. I guess ultimately, it depends on the type of problem you want to solve. Reach out to me if you want to prototype it with me.

katamari-damacy 2y ago
that's more fit for agents, no?
- jeswin 2y ago
  You're right that it's technically orthogonal to what's in the paper. I was trying to model the "reasoning process", which has general applicability depending on how/where it's implemented.
viraptor 2y ago
Reminds me of what plandex does. https://plandex.ai/ https://plandex.ai/ It already does the automatic "does this need splitting into subtasks, or can it be solved immediately" processing.
cube2222 2y ago
I think the problem with long chains of steps on their own (without the bfs stuff) is that your failure probability quickly grows to unreasonable levels. Basically, if each step has a 97% chance of being completed correctly, if your task requires 10 steps one after the other, the chance of success falls to 97%*10=74% If I understand correctly, part of the point of the BFS is to throw compute at it, in order to lower the failure rates. Kind of a "run many times in parallel and pick the best one". This can be effective, but also quite expensive, as seen in the costs OpenAI had to pay for their ARC-AGI benchmarking runs.
dietr1ch 2y ago
I feel humans like doing something in between, maybe a bit like A* would do sometimes.I wouldn't call it A* because of the lack of a consistent heuristic and also lack of strictly numeric evaluation, but it's an in-between DFS and BFS for sure (as is every tree search algorithm?). We go deep while we think it's a good lead, because so far things make sense and it'll be less work, but at some point we start questioning our decisions early in the descent and try alternatives.
- verdverm 2y ago
  You may find Prioritized Grammar Enumeration as an interesting in-between DFS/BFS algorithm https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_gecco2013.pdf https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
wafflemaker 2y ago
How do you understand instinct? I bought a new SSD drive for an old laptop to avoid buying a new one, (x230 has amazing keyboard) but left to another country for Christmas. My intuition told me to take it with me, but logical sense said there will be no time for such things as moving OS to a new drive. My flight back to the work country got cancelled due to fog and I ended up spending a week longer at in-laws place, with plenty free time. A new 512GB drive would help me studying, giving plenty space for school VMs.
kurthr 2y ago
The classic thing people say is "asking the right question" gets you half way there. Your approach sounds like something I call "getting to No" for a problem. It's sort of a combination of "getting to know" and the opposite of the salesman's "getting to Yes". When it works, it's the fastest way to prune off obligations. The goal is to figure out why some particular problem: isn't really a problem, doesn't need to be solved, can't be solved that way, can't really be solved (because of physics or it's really a different problem). As you define the problem better, you can rule each one out to find, the "real" problem, that you CAN solve, and at least one path forward. There's still many ways that it might not be the optimal path, but you know roughly how to get to somewhere better. It also trains you to see around obstacles to success. I've found that some of the best work I've done (especially on acquisitions) was in defining why NOT to do something that looked like a good idea (or particularly interesting to work on) from the onset, but was destined to fail or required unknown HW technology. Frankly, looking >5 years out feels like a coin flip, because some other competing technology could come along before you can get to production.
torginus 2y ago
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.
kordlessagain 2y ago
Your "Tree of failures" approach aligns with how natural cognition seems to work at the edge of comprehensibility. Rather than exhaustively searching (BFS), we use instinct for immediate steps while maintaining a lower-resolution model of longer-term possibilities. The key insight about storing failures rather than successes is particularly interesting - it's more efficient to remember what doesn't work and let patterns emerge naturally from the remaining space. This maps to what I've been exploring with edge cognition and semantic anchoring - using fast set operations to quickly eliminate known bad paths (your failure tree) while allowing the system to explore promising directions using more expensive operations only when needed. The instinct fall-off you describe mirrors our observation about the relationship between computational load and pattern recognition. As distance increases, we need more efficient ways to prune the search space rather than trying to maintain high-resolution understanding throughout. My gut says optimizing on the amount of compute used to do the search (and the inference) is maybe something worth exploring.

by jeswin 2y ago

katamari-damacy 2y ago

that's more fit for agents, no?

jeswin 2y ago
You're right that it's technically orthogonal to what's in the paper. I was trying to model the "reasoning process", which has general applicability depending on how/where it's implemented.

viraptor 2y ago

Reminds me of what plandex does. https://plandex.ai/ https://plandex.ai/ It already does the automatic "does this need splitting into subtasks, or can it be solved immediately" processing.

cube2222 2y ago

I think the problem with long chains of steps on their own (without the bfs stuff) is that your failure probability quickly grows to unreasonable levels. Basically, if each step has a 97% chance of being completed correctly, if your task requires 10 steps one after the other, the chance of success falls to 97%*10=74% If I understand correctly, part of the point of the BFS is to throw compute at it, in order to lower the failure rates. Kind of a "run many times in parallel and pick the best one". This can be effective, but also quite expensive, as seen in the costs OpenAI had to pay for their ARC-AGI benchmarking runs.

dietr1ch 2y ago

I feel humans like doing something in between, maybe a bit like A* would do sometimes.I wouldn't call it A* because of the lack of a consistent heuristic and also lack of strictly numeric evaluation, but it's an in-between DFS and BFS for sure (as is every tree search algorithm?). We go deep while we think it's a good lead, because so far things make sense and it'll be less work, but at some point we start questioning our decisions early in the descent and try alternatives.

verdverm 2y ago
You may find Prioritized Grammar Enumeration as an interesting in-between DFS/BFS algorithm https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_gecco2013.pdf https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...

wafflemaker 2y ago

How do you understand instinct? I bought a new SSD drive for an old laptop to avoid buying a new one, (x230 has amazing keyboard) but left to another country for Christmas. My intuition told me to take it with me, but logical sense said there will be no time for such things as moving OS to a new drive. My flight back to the work country got cancelled due to fog and I ended up spending a week longer at in-laws place, with plenty free time. A new 512GB drive would help me studying, giving plenty space for school VMs.

kurthr 2y ago

The classic thing people say is "asking the right question" gets you half way there. Your approach sounds like something I call "getting to No" for a problem. It's sort of a combination of "getting to know" and the opposite of the salesman's "getting to Yes". When it works, it's the fastest way to prune off obligations. The goal is to figure out why some particular problem: isn't really a problem, doesn't need to be solved, can't be solved that way, can't really be solved (because of physics or it's really a different problem). As you define the problem better, you can rule each one out to find, the "real" problem, that you CAN solve, and at least one path forward. There's still many ways that it might not be the optimal path, but you know roughly how to get to somewhere better. It also trains you to see around obstacles to success. I've found that some of the best work I've done (especially on acquisitions) was in defining why NOT to do something that looked like a good idea (or particularly interesting to work on) from the onset, but was destined to fail or required unknown HW technology. Frankly, looking >5 years out feels like a coin flip, because some other competing technology could come along before you can get to production.

torginus 2y ago

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.

kordlessagain 2y ago

Your "Tree of failures" approach aligns with how natural cognition seems to work at the edge of comprehensibility. Rather than exhaustively searching (BFS), we use instinct for immediate steps while maintaining a lower-resolution model of longer-term possibilities. The key insight about storing failures rather than successes is particularly interesting - it's more efficient to remember what doesn't work and let patterns emerge naturally from the remaining space. This maps to what I've been exploring with edge cognition and semantic anchoring - using fast set operations to quickly eliminate known bad paths (your failure tree) while allowing the system to explore promising directions using more expensive operations only when needed. The instinct fall-off you describe mirrors our observation about the relationship between computational load and pattern recognition. As distance increases, we need more efficient ways to prune the search space rather than trying to maintain high-resolution understanding throughout. My gut says optimizing on the amount of compute used to do the search (and the inference) is maybe something worth exploring.