LLMs Are Randomized Algorithms

Large Language Models (LLMs) function as a type of randomized algorithm, a concept from a 50-year-old academic field. This connection stems from how LLMs generate text by making a probabilistic choice for the next word rather than always selecting the most likely option. This non-determinism is intentionally engineered into the models to improve their performance. By sampling from the probability distribution, an LLM can avoid being consistently wrong when its top prediction is only marginally better than a correct, but slightly less probable, alternative. This trade-off increases the probability of being right in worst-case scenarios at the expense of certainty in best-case ones.