Timely Language Generation Under Global Preference Ordering

A recent theoretical study published on arXiv (2605.11302) examines language generation based on a global preference ordering for strings, a concept introduced by Kleinberg and Wei. The researchers add a crucial element of timeliness, requiring that higher-ranked strings be produced before a deadline determined by a function that relates a string's rank to its required generation time. This requirement aligns with machine learning's tendency to prefer simpler or more plausible outputs. The findings indicate that timely generation is unfeasible for eventually consistent generators, which have been the focus of previous research. However, by slightly relaxing the consistency requirement—allowing a hallucination rate that diminishes over time—the authors show that generation is possible.