5 ms·
Search is almost certainly necessary, and I think the trillion dollar cluster maximalists probably need to talk to people who created superhuman chess engines t
by salamo 2y ago
Search is almost certainly necessary, and I think the trillion dollar cluster maximalists probably need to talk to people who created superhuman chess engines that now can run on smartphones. Because one possibility is that someone figures out how to beat your trillion dollar cluster with a million dollar cluster, or 500k million dollar clusters.
On chess specifically, my takeaway is that the branching factor in chess never gets so high that a breadth-first approach is unworkable. The median branching factor (i.e. the number of legal moves) maxes out at around 40 but generally stays near 30. The most moves I have ever found in any position from a real game was 147, but at that point almost every move is checkmate anyways.
Creating superhuman go engines was a challenge for a long time because the branching factor is so much larger than chess.
Since MCTS is less thorough, it makes sense that a full search could find a weakness and exploit it. To me, the question is whether we can apply breadth-first approaches to larger games and situations, and I think the answer is clearly no. Unlike chess, the branching factor of real-world situations is orders of magnitude larger.
But also unlike chess, which is highly chaotic (small decisions matter a lot for future state), most small decisions don't matter. If you're flying from NYC to LA, it matters a lot if you drive or fly or walk. It mostly doesn't matter if you walk out the door starting with your left foot or your right. It mostly doesn't matter if you blink now or in two seconds.
- cpill 2y agoI think the branching factor for LLMs is around 50k for the number of next possible tokens.
- refulgentis 2y ago100%, GPT-3 <= x < GPT-4o, 100,064, x = GPT-4o, 199,996. (My EoW emergency was the const Map that stored them broke the build, so these #s happen to be top of mind)
- kippinitreal 2y agoI wonder if in an application you could branch on something more abstract than tokens. While there might by 50k token branches and 1k of reasonable likelihood, those actually probably cluster into a few themes you could branch off of. For example “he ordered a …” [burger, hot dog, sandwich: food] or [coke, coffee, water: drinks] or [tennis racket, bowling ball, etc: goods].
- sunnynagam 2y agoI was thinking along the same lines and I think where I end up is realizing searching though the possible space of token sequences isn't the way to do it as the text output space is too far removed from the ground truth for humans. As in text is already a biased projection of reality by humans, now we're searching through an LLM's crude estimation of a biased projection of this? I think a deeper architectural change involving searching internally in the latent space of a model is required. That way we could search in "thought space" instead of "text space" and maybe then only convert the output to text after searching.
- Hugsun 2y agoMy guess is that it's much lower. I'm having a hard time finding a LLM output logit visualizer online, but IIRC, around half of tokens are predicted with >90% confidence. There are regularly more difficult tokens that need to be predicted but the >1% probability tokens aren't so many, probably around 10-20 in most cases. This is of course based on the outputs of actual models that are only so smart, so a tree search that considers all possibly relevant ideas is going to have a larger amount of branches. Considering how many branches would be pruned to maintain grammatical correctness, my guess is that the token-level branching factor would be around 30. It could be up to around 300, but I highly doubt that it's larger than that.
- deleted 2y ago[deleted]