3 ms·

Sure, beam search makes the result less greedy than it originally was, but it’s still an extremely greedy approach overall. It would be sort of like trying to

Sure, beam search makes the result less greedy than it originally was, but it’s still an extremely greedy approach overall. It would be sort of like trying to make local optimization techniques less local by running the process multiple times from different starting points and choosing the minimal basin the process ended up in from out of the different runs. Quite a bit better, but in many cases not even close to the global optimum*. For a slightly more apt analogy, it would be like: 1) Choose multiple starting points 2) For each starting point, perform local optimization until you get stuck in a basin (local minimum) 3) Keep the n overall lowest points, create m different perturbations for each point that pushes the point out of its basin, and go to 1), using these m*n points as your new set of starting points for the next round. Note this process is totally agnostic to whatever the local optimization algorithm is. That’s why I called the beam search part of an LLM’s post-training prediction a “meta-model”, because it doesn’t matter if the core inference is performed by a transformer architecture or something entirely different. *I say “in many cases”. But I am extremely curious for this particular case of inferring sequences of human-generated text the degree to which we fail to capture the true joint probability distribution via single-token prediction + beam search. It’s quite possible we are very far off—perhaps this is the missing “ingredient” for generalized reasoning. On the other hand, as I said in my original post, I never would have guessed current SOTA LLMs only use single-token prediction, and I’m astonished they work as well as they do based on that, so maybe we’re not actually too far off. Without further research, it’s just speculation either way though.

henderson98 2y ago
Hmm, I may have misundertood this, but isnt this just beam search but multiple times(* possibly). Also usually the search is over the discrete token space directly, I am not sure if there are continous surrogates which translate the discrete inference problem(combinatorial) to a continous one, which fit better with your local minima, and perturbation terminology. Although I am uncertain about the utility of beam search run multiple times, I am keen to research literature casting the inference search problem as a continous one. *This might be just a detail/semantics, but for example, for a 3 word context, your starting points may look like "[some token][empty][empty]". Here your procedure simply reduces to a single run of beam search, not multiple, since beam search optimises locally for every turn, producing n different "perturbations" every turn. Let me know if I misunderstood you on this. But inference combinatorial optimisation as a continous surrogate(which sounds like what you are conveying, and will naturally result in starting points as sentences and not just incomplete words/sequences) is something I never considered. There must be some literature around on this....lets see.

henderson98 2y ago

Hmm, I may have misundertood this, but isnt this just beam search but multiple times(* possibly). Also usually the search is over the discrete token space directly, I am not sure if there are continous surrogates which translate the discrete inference problem(combinatorial) to a continous one, which fit better with your local minima, and perturbation terminology. Although I am uncertain about the utility of beam search run multiple times, I am keen to research literature casting the inference search problem as a continous one. *This might be just a detail/semantics, but for example, for a 3 word context, your starting points may look like "[some token][empty][empty]". Here your procedure simply reduces to a single run of beam search, not multiple, since beam search optimises locally for every turn, producing n different "perturbations" every turn. Let me know if I misunderstood you on this. But inference combinatorial optimisation as a continous surrogate(which sounds like what you are conveying, and will naturally result in starting points as sentences and not just incomplete words/sequences) is something I never considered. There must be some literature around on this....lets see.