A minute of math on the channel, while I’m over there looking at what questions who wrote, I’ll start answering sometime during the week.
Recently, like I said, I talked about ICL, I’m prepping a proper piece for here to post. And there, before me and my little talk, there was this nod to the idea that like, in LLMs everything is sooo non-deterministic. To which I objected, like no, not really, it’s the interpretation that sucks, and in general if you do token sampling by the highest probability — the degree of, so to speak, “random” drops really low. And I decided, overall, I’m thinking, let me see just how much math can squeeze certain types of tasks where there’s a lot of randomness down to clear determinism. And it turned out, actually, the question is solved.
For a 1994 paper, he and the computer scientist Noam Nisan illuminated that connection. They proved that if any natural hard problems exist, as most computer scientists suspect, then every efficient randomized algorithm can be replaced by an efficient deterministic one. “You can always eliminate randomness,” Wigderson said.
Source (https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/)
Original (RU)
Минутка математики в канале, пока я там смотрю какие, кто вопросы написал, возьмусь отвечать где-то на неделе.
Недавно как я и говорил рассказывал про ICL, готовлю нормальный материал сюда чтобы выложить. И там до меня и моего рассказа была отсылка к тому, что мол в LLM все ой как недетерминировано. На что я возразил, что мол не так, а интерпретация страдает, да и в целом если сэмплинг токенов сделать по самой высокой вероятности - степень так сказать рандома упадет очень низко. И решил в целом думаю посмотрю, а насколько математика может сводить определенные типы задач где много рандома к четкому детерминизму. И оказалось, что вообще-то вопрос решен.
For a 1994 paper, he and the computer scientist Noam Nisan illuminated that connection. They proved that if any natural hard problems exist, as most computer scientists suspect, then every efficient randomized algorithm can be replaced by an efficient deterministic one. “You can always eliminate randomness,” Wigderson said.
Источник (https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/)