15 papers
Optimistic Rates for Multiclass PAC Learning
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales w…
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation
Xiaoyu Li, Andi Han, Dai Shi +2
Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimensi…
IRIS: Visual-Semantic Binding for Forgery-Resistant Watermarking of Diffusion Images
Xiaoyan Feng, Zheng Gao, Tong Guan +4
Most in-generation diffusion watermarks embed patterns independent of the image that carries them, and attackers transplant the marks onto images the generator did not produce, res…
Watermark Forensics for Generative Models: An Information-Theoretic Perspective
Xiaoyu Li, Zheng Gao, Xiaoyan Feng +3
The paper studies how to embed and detect watermarks in the outputs of generative language models, providing an information‑theoretic analysis of the trade‑offs for detection, attr…
TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories
Zheng Gao, Xiaoyu Li, Xiaoyan Feng +5
LLM agents reach users through resellers, who may rebrand a developer's agent or substitute a cheaper model. When provenance is disputed, attribution rests on the trajectory log (t…
The Exact Worst-Case Tail Probability under Bounded Kurtosis
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
We determine exactly what a kurtosis bound buys for one-sided tail control. For the class of real random variables with mean , variance , and fourth moment…