Language Models Demand New Computer Science

The emergence of large language models (LMs) as versatile problem-solving systems marks a paradigm shift comparable to the advent of digital computers. Traditional computer science provides theoretical foundations for understanding computational processes through complexity theory, algorithms, and formal methods, this position paper argues that language models require their own distinct theoretical framework, termed as Computer Science of Language Models (CSLM). We identify seven fundamental differences between traditional computing and language model: 1) the generating-solving-verifying triad versus the solving-verifying dichotomy, 2) token-based rather than operation-based computation, 3) probabilistic reliability with hallucinations rather than deterministic correctness, 4) native multimodal understanding beyond pixel-level processing, 5) general-purpose capabilities versus problem-specific algorithms, 6) essential two-stage training-inference processes, and 7) inherent knowledge. We argue these differences necessitate new theoretical frameworks, complexity measures, and evaluation methodologies. Then, we define the token complexity as the core concept in CSLM and discuss connections to existing research in scaling laws, memory systems, tool use, and fine-tuning, while identifying critical open questions about LM-complete problems, reliability bounds, emergence phenomena, and multimodal complexity. Drawing parallels to complexity theory's 50-year development, we present a 5-year research roadmap (2026-2030) to build the mature CSLM. CSLM promises to transform LM development from empirical scaling to principled engineering grounded in rigorous theory and strengthen our understanding about both the problems, LMs and their relationships.