Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

arXiv:2608.01320 · cs.DS, cs.AI, cs.CL, cs.DM, cs.LG · Submitted 2026-08-02 · Read on arXiv

Ziyi Cai, Shuangping Li, Yiheng Shen, Kangning Wang, Peng Zhang

cs.DS, cs.AI, cs.CL, cs.DM, cs.LG

Submitted: 2026-08-02

Project page: https://languagegeneration.github.io

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Generator — 16× in this paper · explained in 2 episodes
• Adaptive Adversaries — 2× in this paper · explained in 1 episode
• Annual ACM Symposium on Theory of Computing — 2× in this paper
• Consistency — 2× in this paper · explained in 3 episodes
• Forty-second International Conference on Machine Learning — 2× in this paper
• Hallucination — 2× in this paper · explained in 4 episodes
• Thirty Eighth Annual Conference on Learning Theory — 2× in this paper
• Unified Framework — 2× in this paper · explained in 5 episodes
• Annual ACM-SIAM Symposium on Discrete Algorithms — 1× in this paper
• Annual Symposium on Foundations of Computer Science — 1× in this paper
• Core — 1× in this paper · explained in 2 episodes
• Differentially Private — 1× in this paper · explained in 3 episodes
• Downstream Tasks — 1× in this paper · explained in 2 episodes
• Embeddings — 1× in this paper · explained in 2 episodes
• Generative Model — 1× in this paper · explained in 2 episodes
• Generative Models — 1× in this paper · explained in 3 episodes
• Mode Collapse — 1× in this paper · explained in 2 episodes
• Resource Constraints — 1× in this paper · explained in 4 episodes
• Robustness — 1× in this paper · explained in 5 episodes

Sources

• On Language Generation in the Limit with Bounded Memory
• Validity, Sparse Holes, and Breadth in Language Generation: Banach Density, Topology, and Geometry
• Language Generation with Infinite Contamination
• Differentially Private Language Generation and Identification in the Limit

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Computational and Statistical Hardness of Calibration Distance
• Edge-Private Matching Kernels Through Local Decoding
• Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing