CSLM

NeurIPS 2026 · Position Paper Track

Language Models Demand New Computer Science

Chang Yang1, Xinrun Wang2,*, Shuxin Li3, Qinggang Zhang4, Huachi Zhou1, Zhuoyi Lin5, Bo Li1, Xiao Huang1

1The Hong Kong Polytechnic University · 2Singapore Management University · 3Nanyang Technological University · 4Jilin University
5Institute for Infocomm Research, A*STAR · *Corresponding author

Our position. Language models are becoming the new universal computer, yet they break nearly every assumption of classical computer science. We can build ever more powerful models, but we cannot predict their behavior, explain their limits or guide their development from first principles. Language models need their own theory: the Computer Science of Language Models (CSLM), built on token complexity.

  1. Why Seven fundamental differences LMs propose problems as well as solve and verify them, compute in tokens, and succeed only with some probability.
  2. How Token complexity Measure an LM system by its curve of tokens against success rate, and build LM-P, LM-NP and LM-Complete on it.
  3. What next Roadmap 2026–2030 From shared definitions, to LM-complete problems, to a scaling law for token complexity.

01Why a New Computer Science: Seven Differences

Language models change three basic assumptions of classical computation: what is computed, in what unit, and how reliably.

The computational model

  1. Propose–solve–verify triad Classical theory compares solving with verifying (P vs. NP). LMs also propose new problems, through conjectures and self-play, so proposal has a cost that can be studied too.
  2. Token as the basic operation The unit of computation is the token, not the arithmetic operation. Models differ in how many tokens a problem takes, and token count sets cost and latency.
  3. Unreliable reasoning LMs hallucinate even when prompted correctly, and their errors fit no fixed noise model. Correctness is a probability, so verification matters more and is harder.

Properties that shape token complexity

  1. Native multimodality Images, audio and video enter the same token stream as text, at the same cost.
  2. General-purpose capabilities One model runs many "algorithms" it learned from data, across tasks.
  3. Training–inference stages Training tokens rewrite the program, changing the inference cost of a fixed problem.
  4. Inherent knowledge Knowledge stored in the weights can help reasoning, or mislead it.
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. Like quantum complexity theory, it extends classical theory rather than contradicting it.

Side-by-side: traditional CS vs. CSLM
AspectTraditional CSCS of Language Models
ParadigmSolving–verifying dichotomyPropose–solve–verify triad
Basic unitComputation operationsTokens
ReliabilityDeterministic, correct if programmed correctlyProbabilistic, can hallucinate
ModalityBits and numbers; pixels without conceptsNative multimodal understanding
ScopeProblem-specific algorithmsGeneral-purpose models
LifecycleInference onlyTraining + inference
KnowledgeData-agnostic at runtimeKnowledge encoded in parameters

02The Core Idea: Token Complexity

Measure a language model system by how many tokens it needs to reach each success rate. The goal: complete tasks correctly with fewer tokens.

𝓜 · System
One or more LMs, with their tokenizers and inference procedure (decoding, sampling, test-time scaling).
I · Instance
A problem instance of size n = |I|, e.g. a list to sort or a SAT formula.
τ · Tokens
The input and output tokens the system spends on I.
p · Success rate
How often an acceptance criterion Ω (exact match, Lean, a rubric, an LLM judge) accepts the output over repeated runs.
Definition · Token Complexity

Token complexity is a curve, not a single number: the minimal input and output tokens needed to reach each success rate.

TokC(I, 𝓜) = { ( τin(I, 𝓜, p), τout(I, 𝓜, p) ) : p ∈ [0, 1] }
Two systems' token complexity curves: A reaches the target success rate with fewer tokens, B needs more tokens but reaches a higher ceiling 1 0 tokens τ → success rate p p* τA τB System A System B
An illustration. At target success rate p*, System A needs τA tokens and System B needs more, but B reaches a higher ceiling. A single accuracy or token count cannot express this trade-off.
System & problem profile

SP(𝓜) gathers one system's curves over all problems. PP(P) gathers one problem's curves over all systems, so systems with different tokenizers are compared without a common unit.

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. Like BPP, both are defined by a fixed threshold p*.

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(|IA|) tokens. Is LM-P = LM-NP?

Why tokens, and not FLOPs?

Access

FLOPs can only be measured for open models. Token usage is observable for any model through its API.

Structure

A token trace records how a model breaks a problem down, backtracks and elaborates, not just how much arithmetic it does.

Stability

FLOPs per token change with speculative decoding and quantization. Token count does not, and it sets latency and cost directly.

Each token costs a bounded number of FLOPs, so token complexity still links to classical bounds. The token-to-operation ratio ρ(n) = τout(n) / TP(n), e.g. τout / (n log n) for sorting, shows whether an LM's gap to the optimal algorithm stays constant or widens as problems grow.

Doesn't the tokenizer change everything?

The tokenizer is part of the system, so token complexity is well defined for any fixed system. Switching between byte-level tokenizers changes token counts by at most a constant factor, which is absorbed into the big-O constant: exponents, and therefore complexity classes, do not depend on the tokenizer. On English text, eight widely deployed tokenizers (GPT-2 to Gemma-2, vocabularies of 32K–256K) agree to within a factor of 1.13×.

A first measurement: sorting

Even on sorting, two models trace clearly different curves. We measured the token complexity of sorting (n = 120, 30 instances) for gpt-5-mini and gpt-5-nano, with up to 16 independent trials per instance and exact-match success.

Accuracy vs. trials, tokens vs. trials, and accuracy vs. tokens for gpt-5-mini and gpt-5-nano on sorting
Left: accuracy vs. trials. Middle: tokens vs. trials. Right: the token complexity curve itself.

03Connections to Existing Research

Scaling laws, memory, tools, agents and fine-tuning all become questions about the same curve: how they move tokens and success rate.

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

Context is the cache, retrieval is the disk, and weights are a tier with no classical counterpart. Compare TokC(I, 𝓜) with TokC(I, 𝓜 ⊕ E) and charge each tier separately.

Tools

A tool call is an oracle query: only the orchestration costs tokens. Building a tool pays off when TokCcreate + Σ TokC(Ii, 𝓜 ⊕ t) < Σ TokC(Ii, 𝓜).

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

Training tokens rewrite the algorithm. Treat "make 𝓜 solve P′ with success rate p" as the instance, and SFT, RL and distillation differ only in the tokens they spend.

04Open Questions & Roadmap 2026–2030

Classical complexity theory went from Turing to Karp in four decades. We propose a five-year roadmap to make CSLM a rigorous discipline.

Open questions

  1. 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 to a few LM-complete ones?
  2. Training dynamics How should compute be split, C = Ctrain + Cinfer? How many tokens does it take to learn a new capability through SFT or RL fine-tuning?
  3. 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?

Roadmap

  1. 1936
    Turing · the Turing machine
  2. 1965
    Edmonds · the class P
  3. 1971
    Cook · the Cook–Levin theorem
  4. 1972
    Karp · 21 NP-complete problems
  5. Computer Science of Language Models
  6. 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).

  7. 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.

  8. 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.

CSLM builds on several lines of work that already bring classical computer science to language models.

Benchmarking LLMs on NP(-complete) problems

Complexity classes give benchmarks a principled difficulty scale and unlimited, verifiable instances. CSLM asks what these benchmarks should report: the full token complexity curve rather than a single accuracy.

  • NPHardEval Problems drawn from P, NP-complete and NP-hard.
  • ZebraLogic Zebra puzzles, an NP-complete task, to see how reasoning scales with difficulty.
  • Sudoku-Bench 2,765 procedurally generated Sudoku instances across difficulty levels.
  • Reasoning Gym Procedural generators and verifiers with adjustable complexity.
  • NPPC 25 NP-complete problems with instances of ever-increasing scale (our work).

NP problems as training environments

Verifiable hard problems are becoming RL environments. In CSLM terms, this training spends tokens to shift a model's inference curve.

  • SATURN SAT-based RL to improve general reasoning.
  • NP-Engine 10 NP-hard tasks with controllable generators and heuristic solvers.
  • SynLogic Synthetic logic tasks that carry over to mathematical reasoning.
  • RLVE Adaptive verifiable environments that calibrate difficulty during RL.
  • SCALER Synthetic, scalable environments with adaptive difficulty.

Algorithmic understanding of LLMs

Expressivity results and interpretability ask which algorithms a model can run and does run. CSLM adds how many tokens running them costs.

Complementary frameworks

These study LMs at other levels. CSLM treats the system as a black box and asks how its token cost scales with the problem, so it applies to open and closed models alike.

  • BAPO bounds Worst-case lower bounds on chain-of-thought length from transformer bandwidth. A white-box instance of the lower bounds CSLM predicts.
  • Physics of Language Models A microscopic view of knowledge storage and reasoning inside the model. CSLM is the macroscopic view.
  • Statistical learning theory Sample complexity counts training examples. Token complexity counts inference cost.

Scaling laws and efficiency

Scaling laws are the first success story of CSLM. We expect analogous laws for token complexity, and efficiency measures that hold across tokenizers.

Memory, tools and fine-tuning

CSLM measures what each addition is worth by comparing TokC(I, 𝓜) with TokC(I, 𝓜 ⊕ E) or TokC(I, 𝓜 ⊕ T), and treats training tokens as rewriting the algorithm.

Perspectives

Broader views on where language model research is heading.

Our work

NeurIPS · 2026

Language Models Demand New Computer Science

Seven fundamental differences, token complexity, and a five-year roadmap for CSLM. Position Paper Track.

 TMLR · 2026

NPPC: an Ever-Scaling Reasoning Benchmark

The Nondeterministic Polynomial-time Problem Challenge scales in difficulty, generates unlimited instances and stays easy to verify.
Overview of the NPPC benchmark
NPPC: an ever-scaling benchmark built on NP-complete problems (arXiv).

Cite & Contact

@inproceedings{yang2026cslm,
  title     = {Language Models Demand New Computer Science},
  author    = {Yang, Chang and Wang, Xinrun and Li, Shuxin and Zhang, Qinggang and
               Zhou, Huachi and Lin, Zhuoyi and Li, Bo and Huang, Xiao},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS), Position Paper Track},
  year      = {2026}
}

Let's build the computer science of language models together. Comments and collaborations are welcome: Chang Yang (chang.yang@connect.polyu.hk) and Xinrun Wang (xrwang@smu.edu.sg).