Position Paper · 2026

Language Models Demand New Computer Science

Language models are becoming the new universal computer. We argue they need their own theory — the Computer Science of Language Models (CSLM).

Traditional computer science gave us complexity theory, algorithms and formal methods for deterministic, operation-based machines. Language models break nearly every one of its assumptions: they generate tokens instead of executing operations, succeed with some probability instead of guaranteeing correctness, understand many modalities natively, and carry vast knowledge in their parameters. As a result, we can build ever more powerful models, but we cannot yet predict their behavior, explain their limits or guide their development from first principles.

7 fundamental differences
Token complexity
Roadmap 2026–2030

Definition (CSLM). The Computer Science of Language Models is a theoretical and empirical framework for understanding computation by language models. It covers complexity analysis, algorithmic behavior, reliability, and how model architectures, training procedures and problem-solving capabilities relate to each other across modalities and tasks.

The goal: complete tasks correctly with fewer tokens, and so move LM development from empirical scaling to principled engineering.

01Seven Fundamental Differences

Generating–solving–verifying triad Classical theory studies how hard it is to solve a problem compared with verifying an answer (P vs. NP). LMs add a third operation, generation: they can propose new problems, so the cost of generating a problem can be studied too.
Token as the basic operation The unit of computation is the token, not the arithmetic operation. Token count sets both cost and latency.
Unreliable reasoning LMs hallucinate even when prompted correctly. Correctness becomes a probability, not a guarantee, which makes verification both more important and harder.
Native multimodality Text, images, audio and video share one representation space, so a model reasons about concepts rather than raw pixels.
General-purpose capabilities One model covers translation, coding, maths and more by running internal "algorithms" it learned from data.
Training–inference stages Training plays the role of programming, but the link from data to behavior is indirect. Scaling laws are the first success story.
Inherent knowledge A sorting algorithm knows nothing about what it sorts. An LM is a knowledge base and a reasoning engine at once, and that knowledge can help or mislead its reasoning.

Aspect	Traditional CS	CS of Language Models
Paradigm	Solving–verifying dichotomy	Generating–solving–verifying triad
Basic unit	Computation operations	Tokens
Reliability	Deterministic, correct if programmed correctly	Probabilistic, can hallucinate
Modality	Bits and numbers; pixels without concepts	Native multimodal understanding
Scope	Problem-specific algorithms	General-purpose models
Lifecycle	Inference only	Training + inference
Knowledge	Data-agnostic at runtime	Knowledge encoded in parameters

02Token Complexity

The central concept of CSLM is token complexity. A language model system (LMS) 𝓜 is made of one or more LMs. On a problem instance I, the system uses τ tokens and succeeds with probability p ∈ [0, 1]. The aim is to minimize tokens while maximizing the success rate.

Definition · Token Complexity

Token complexity is a curve, not a single number. It is the set of achievable (tokens, success rate) pairs:

TC(I, 𝓜) = { ( τⁱⁿ(I, 𝓜, p), τ^out(I, 𝓜, p) ) : p ∈ [0, 1] }

Tokens are not uniform: one token can cost more compute or carry more information than another. Classical complexity faces the same issue, since a single "operation" in the RAM model can be a cache hit or a floating-point division. The abstraction still works because what matters is how the count scales, not the constant factors.

System card & problem card

SC(𝓜) gathers the token complexity of one system over all problems. PC(P) gathers the token complexity of one problem over all systems.

Asymptotic token complexity

𝓜 solves P in O(f(n)) tokens at success rate p* if τ^out ≤ C·f(|I|) for all large enough instances.

LM-P & LM-NP

LM-P: problems an LMS can solve with poly(|I|) tokens at success rate ≥ p*. LM-NP: problems whose solutions can be verified with poly(|I|) tokens.

LM-Complete & reductions

A problem in LM-NP is LM-Complete if every LM-NP problem reduces to it token-efficiently, i.e. A ≤_T B using poly(|I_A|) tokens. Is LM-P = LM-NP?

Why tokens, and not FLOPs?

The FLOPs needed per token depend on the inference stack (speculative decoding changes them, for example), and FLOPs cannot be observed at all for closed models. Token count does not depend on the inference framework, it is always observable, and it directly sets cost and latency. It also records the structure of the reasoning: how a model breaks a problem down, backtracks and elaborates. The token-to-operation ratio τ^out / (n log n) for sorting links token complexity to classical algorithmic complexity.

03Connections to Existing Research

Token complexity gives existing lines of LM research a common language:

Connections between CSLM and existing CS and LLM research — Left: links to classical CS. Right: links to LLM research.

Scaling laws

Training laws over (N, D, C) may carry over to token complexity. Inference scaling, p ∼ (τ^out)^β, is a direct trade-off between tokens and success rate.

Memory

Compare TC(I, 𝓜) with TC(I, 𝓜 ⊕ E), where E is external memory. Retrieval spends tokens but can raise p. Self-evolving memory adds summarization and reflection costs.

Tools

Tools take heavy computation off the model. Building a tool pays off when TC_create + Σ TC(I_i, 𝓜 ⊕ t) < Σ TC(I_i, 𝓜).

Multi-agent systems

System-level token complexity depends on three things: how the task is split, which model handles each part, and how much the agents need to communicate.

Fine-tuning

Treat "make 𝓜 solve P′ with success rate p" as the instance. TC then measures exploration cost, sample efficiency and convergence in RL fine-tuning.

A first experiment

On sorting (n = 120), gpt-5-mini and gpt-5-nano trace clearly different accuracy-vs-token curves: ≈110K vs. ≈280K tokens at 16 trials.

04Open Questions

Complexity and hardness What is the LM analogue of SAT? Are there problems that need exponentially many tokens to solve but only polynomially many to verify? Can hard problems be reduced systematically to a few LM-complete ones?
Training dynamics How should compute be split, C = C_train + C_infer? How many tokens does it take to learn a new capability through SFT or RL fine-tuning?
Memory, tools and agents How do we measure what these add to token complexity? When is it better to scale up parameters than to give a model external resources?

05Roadmap 2026–2030

Classical complexity theory took decades to mature. We propose a five-year roadmap to make CSLM a rigorous discipline.

1936
Turing · the Turing machine
1965
Edmonds · the class P
1971
Cook · the Cook–Levin theorem
1972
Karp · 21 NP-complete problems
Computer Science of Language Models
2026
Foundations & formalization
Agree on how to count tokens across prompts, retrieved context and chain-of-thought. Fix the definitions of LM-P, LM-NP and LM-Complete. Prove the first lower bounds, and publish benchmarks with asymptotic instance generators (sorting, SAT, graph coloring, TSP, knapsack).
2027–28
Classification & structural theory
Find LM-complete problems, or prove none exist. Build a reduction framework covering 25+ problem classes. Prove unconditional lower bounds, and extend the theory to multimodal inputs and RL fine-tuning.
2029–30
Maturity & integration
Settle, or formally characterize, LM-P vs. LM-NP. Map the reliability cliff: the point where p = 0.99 needs exponentially more tokens than p = 0.5. Derive a universal token-complexity scaling law, a Chinchilla law for CSLM. Launch CSLM-Bench.

06Our Work

Position · 2026