> Backtracking assumes depth-first search, which isn't strictly needed as you could explore all possible options in parallel in a breadth-first manner You coul

> Backtracking assumes depth-first search, which isn't strictly needed as you could explore all possible options in parallel in a breadth-first manner You could in theory, but it'd be massively/prohibitively more expensive - exploring a whole tree just to end up using a single branch. It'd be like trying to have a computer play chess by evaluating EVERY branching position out to some fixed depth, rather than using MCTS to prune away unpromising lines. Not only that, but reasoning in general (of which LLM-based reasoning is only a limited case) isn't just about search - it can also require exploration and acquisition of new knowledge if you run into an impasse that your past experience can't handle. If AI systems hope to achieve human-level AGI, they will need to change to support continuous learning and exploration as a part of reasoning, which naturally means more of a depth-first approach (continue until you hit an impasse) with backtracking. You can say that hallucination is due to gaps in the training set, but of course humans don't have that problem because we know what we know, and have episodic memories of when/where/how we learned things. LLMs have none of that.