主题：Computer Science of Language Models

嘉宾：王新润  新加坡管理大学 助理教授

时间：2026年7月1日 下午15:00-16:00

地点：华中科技大学东校区 计算机学院大楼 2039会议室

报告摘要：

Large language models have become general-purpose problem solvers, a shift as consequential as the arrival of the digital computer. Yet the theoretical scaffolding we built for classical computing — complexity classes, algorithm analysis, formal correctness — doesn't quite fit them. In this talk, I argue that language models deserve a theoretical discipline of their own, which I call the Computer Science of Language Models (CSLM).

I'll start from seven ways LMs depart from traditional computation: they generate, solve, and verify rather than merely solve and verify; they compute in tokens rather than operations; they are probabilistically reliable and prone to hallucination rather than deterministically correct; they understand multimodal input natively; they are general-purpose rather than problem-specific; they depend on a coupled training–inference process; and they carry inherent knowledge. Each of these breaks an assumption that classical theory takes for granted, and together they motivate new complexity measures and evaluation methods.

At the center of the proposal is token complexity — a candidate analogue to time and space complexity for the LM era. I'll connect it to active threads in scaling laws, memory, tool use, and fine-tuning, and lay out the open problems I find most pressing: what an "LM-complete" problem might be, where reliability bounds come from, how emergence should be characterized, and how to reason about multimodal complexity.

Complexity theory took fifty years to mature; I'll close with a five-year roadmap (2026–2030) for getting CSLM off the ground — and an argument for why moving from empirical scaling to principled, theory-grounded engineering would change how we understand both these models and the problems we ask them to solve.

报告人简介：

Xinrun Wang is currently an Assistant Professor in the School of Computing and Information Systems (SCIS) at Singapore Management University (SMU). Prior to joining SMU, he was a Research Assistant Professor in Nanyang Technological University (NTU) since 2021. Before that, He was a Research Fellow in NTU. He received PhD from NTU in 2020, supervised Prof. Bo An. His research interests are game theory, (multi-agent) reinforcement learning, and foundation models for decision making. His work won the outstanding student paper award in GameSec 2019. He received the Lee Kong Chian Fellow (2025-2027).