Token Space: A Category Theory Framework for AI Computations

Wuming Pan

math.GMApr 11, 2024

Token Space: A Category Theory Framework for AI Computations

Authors: Wuming Pan

Organizations: College of Computer Science, Sichuan University, Chengdu, P.R. China, 610065

Abstract

We introduce Token Space, a categorical framework for AI computations based on explicit structural records. Five theses guide it: object interiors should be data; category theory should compute with its own objects; computational interfaces should specify structural obligations; equal vectors need not identify the same Token occurrence; and computation should admit an unbounded, dynamically organized population of Token computing cores. A Token is a finite tuple of carrier elements and fixed symbols. A Token class pairs a carrier with a heap of records; Token maps preserve those records. The elementary category has finite limits, finite coproducts and exponentials, but is not a topos. Algebraic tokenization is fully faithful for a fixed finitary signature with all homomorphisms. Small categories and functors have record encodings, natural transformations have endpoint-constrained encodings, and finite categorical constructions are executable. Operators and supported tree reification expose internal structure. For represented finite mappings, valid acyclic graphs evaluate through unique Token maps. Completed parts glue by pullback-pushout squares, sharing induces an adjunction on completion lattices, frontier interfaces form a functor, and certified residual replacement preserves the remaining result. Effective finite transitions preserve finite configurations; a uniform generator yields arbitrarily wide ready populations. Requests with finite dependency closures complete under stated progress conditions. Transformers are one implementation family: permutation heaps characterize equivariance and prefix-agreement heaps characterize causality under specified interfaces. Structural distillation uses teacher-induced heaps; relation-saturating quotients characterize exact preservation and reflection of recorded structure.

Figures & tables

Construction	Mathematical contribution	Computational purpose
Sets and functions	A carrier $B$ and transformations $f:B\to C$ .	Specify inputs, states, outputs, and their extensional behavior.
Fixed core	Add $E$ ; use $f\sqcup\mathrm{id}_{E}$ on $B\sqcup E$ .	Separate transformable data from fixed relation names, operators, and protocol labels.
Finite words	Form $F_{E}(B)=(B\sqcup E)^{*}$ .	Supply ordered records with repeated entries and explicit labels.
Selected heaps	Choose $H\subseteq F_{E}(B)$ .	State which connections, dependencies, operation graphs, or constraints belong to this description.
Subsets extension	Require $F_{E}(f)(H)\subseteq K$ .	Select the computations and translations that preserve the specified records.
Products and exponentials	Combine interfaces and obtain map objects with evaluation.	Organize parallel composition, parameterized computation, and maps treated as data.

Table 1: Construction of Token Space and the role of each step. The last two rows are constructions within, or extensions of, the elementary framework; their properties require their own proofs.

Question	Diagram to consult	What its arrows express
What does a Token map preserve?	Figure 1	An ambient carrier function transports each selected record.
How is a natural transformation data?	Figure 3	A lift between encoded categories has prescribed endpoint functors.
Why can independent work be joined?	Figures 5 and 6	Completed classes embed and glue; their values agree.
Why does expansion retain behavior?	Figure 7	Changing a description commutes with evaluation.
How do live interfaces change?	Figure 8	Frontier advancement composes and preserves the remaining output.
What work can sharing reuse?	Figure 9	Images of completed sets and consistent values transfer together.

Table 2: A reading route through the categorical diagrams. The diagrams specify their objects and maps; the associated propositions establish their commutativity or universal properties.

Object	Mathematical representation	Role in a language model or in Token Space
Tokenizer token type	$v\in V$	A vocabulary entry; its ID specifies an embedding-table lookup.
Token occurrence	$o=(s,i)$ with value $v_{i}$	One occurrence at a particular input position; repeated IDs give different occurrences.
Input embedding	$e(v_{i})\in\mathbb{R}^{d}$	A learned vector associated with the vocabulary item, before contextual mixing.
Located hidden state	$\omega=(\theta,\ell,s,i,h_{i}^{(\ell)}(s))$	A state occurrence with its model, layer, input, and position; its vector alone omits this location.
Sequence state	$H^{(\ell)}\in(\mathbb{R}^{d})^{n}$	The input or output of a Transformer block. This is one carrier element in the sequence classes used below.
Structural Token	$r\in\Upsilon\subseteq(B\sqcup E)^{*}$	A finite record in the mathematical description, such as $(c_{k},H,H^{\prime})$ or $(\mathrm{next},o_{i},o_{i+1})$ .

Table 3: The objects called “tokens” in informal discussion occupy distinct levels. A Token class is an object of

\mathsf{TS}_{E}

; an individual structural Token is an element of its heap.

Panel of Figure 1 — Figure 1: The record-preservation square in $\mathbf{Set}$ for a carrier function $f:A\to B$ . A Token map exists exactly when $F_{E}(f)$ restricts to the displayed $p$ . The carrier function $f$ remains part of the map; the restriction $p$ alone can lose information, as Example 4.3 shows.

Construction	Carrier	Heap and computational role
Initial object $0_{E}$	$\varnothing$	Empty heap. The empty interface has a unique map into any class.
Terminal object $1_{E}$	$\{*\}$	$F_{E}(\{*\})$ . A target for discarding an input; maps out of it select global elements.
Product	$A\times B$	$F_{E}(\pi_{A})^{-1}(H_{A})\cap F_{E}(\pi_{B})^{-1}(H_{B})$ . Combines two interfaces with matched record shapes.
Coproduct	$A\sqcup B$	$F_{E}(\iota_{A})(H_{A})\cup F_{E}(\iota_{B})(H_{B})$ . Keeps alternatives tagged, with casewise maps.
Equalizer of $f,g$	$A_{0}\subseteq A$	$H_{A}\cap F_{E}(A_{0})$ , where $A_{0}=\{a:f(a)=g(a)\}$ . Restricts the interface to agreement states.
Exponential $T_{B}^{T_{A}}$	$B^{A}$	$H_{B}\vartriangleleft H_{A}$ , defined in ( 4 ). Supports evaluation and currying; its global elements are the admissible maps.

Table 4: Elementary Token Space: carriers, heaps, and uses of the universal constructions. A carrier element of the exponential need not be a global element. There is no subobject classifier for this category.

Panel of Figure 2 — Figure 2: An operation homomorphism as a square in $\mathbf{Set}$ . Applying the operation and then $f$ agrees with transforming its operands first. For $k=0$ , the left-hand objects are singleton sets and the same square expresses preservation of a constant.

Panel of Figure 3 — Figure 3: A natural transformation as a lift with fixed endpoints in $\mathsf{TS}_{E_{\mathrm{cat}}}$ . Here $d,c:\mathbf{D}^{\to}\to\mathbf{D}$ are the endpoint functors, and $\otimes$ is the Token Space product. An endpoint pair alone does not specify a lift; its existence and choice encode the natural transformation.

Name	Symbol	Effect
Merging / meeting / deleting	$\Cup,\ \Cap,\ \ominus$	Union, intersection, difference of heaps (and bases).
Forgetting / stuffing / abstracting	$\varnothing,\ \circledast,\ \circledcirc$	Empty the heap; fill the heap; make the heap the base.
Matchup (product)	$\otimes$	Carrier $B_{1}\times B_{2}$ ; a Token iff both projections are Tokens.
Blending (extending product)	$\oplus$	Carrier $B_{1}\times B_{2}$ ; a Token iff some projection is a Token.
Union / Y-union	$\uplus$	Tagged union of bases and heaps.
Referring (exponential)	$\vartriangleleft$	Carrier $B_{1}^{B_{2}}$ ; heap $\Upsilon_{1}\vartriangleleft\Upsilon_{2}$ of ( 4 ).

Table 5: The operator calculus on Token classes.

Representation	What is stored	How evaluation proceeds
Explicit table	One output for each encoded input.	Index or search the table.
Circuit	Primitive operations and directed connections.	Evaluate nodes in dependency order.
Decision diagram	Tests, branches, and shared subgraphs.	Follow the tests selected by the input.
Factorized calculation	Factors and compatible intermediate interfaces.	Execute the factors without materializing their composite table.
Parameterized model	Architecture, numerical parameters, and an execution protocol.	Run the prescribed numerical operations.
Hybrid description	Typed components in several representations.	Dispatch their evaluators and compose the results.

Table 6: Representation choices for finite mappings. Expressivity, correctness and cost must be established for each choice; none is assumed universally compact.

Representation of $P_{n}$	Storage under the specified encoding	Evaluation work
Full output table	$n2^{n}$ output bits	One table access plus input indexing and $n$ output bits.
Separate prefix expression trees	$O(n^{2}\log n)$ bits using indexed variables	$n(n-1)/2$ XOR calls.
Shared prefix graph	$O(n\log n)$ bits using node indices	$n-1$ XOR calls plus output access.

Table 7: A family with explicitly proved sharing and cost bounds. These are costs of particular encodings and evaluators, not representation-independent lower bounds.

Panel of Figure 4 — Figure 4: A partial execution extends without changing completed values. The objects and arrows lie in $\mathsf{TS}_{E}$ . The arrow across the top enlarges the completed structure; the arrows into $\mathcal{A}_{a}$ assign its values. Commutativity is the invariant ( 16 ).

Panel of Figure 5 — Figure 5: Two completed parts are joined along their common completed part. This square is bicartesian: it has both the pullback and pushout universal properties. These properties refer to entire Token classes and their maps; the square does not assert a hardware synchronization mechanism.

Panel of Figure 6 — Figure 6: The execution diamond for two simultaneously ready nodes. The labels $+u,+v$ name extensions by a completed operation; the arrows themselves are inclusions. Together with Figure 4 , the square says that either order, or their ready batch, gives the same structure and the same values.

What changes	What stays fixed	Required mechanism or invariant
Worker allocation	The graph, its input and output behavior	Readiness-based scheduling, retained values and continued progress.
Active work	The requested result of one invocation	Demand propagation, branch selection, node lifetimes and valid residual computations.
Representation and granularity	The denoted mapping at the chosen interface	Certified implementations in $\mathsf{Impl}(f)$ ; a migration condition for a running invocation.
Input or interface size	A specified uniform family or protocol	Effective construction of the family and any required cross-size compatibility.

Table 8: Computational elasticity has several distinct objects. More workers, more active nodes, a larger description and a larger input domain are different changes.

Panel of Figure 7 — Figure 7: Module expansion commutes with evaluation in $\mathbf{Set}$ . Here $\mathcal{R}_{\mathcal{M}}^{n,m}$ and $\mathcal{R}_{\Omega}^{n,m}$ are valid coded descriptions at the fixed interface, for the fixed library and for primitive graphs respectively. Theorem 10.12 proves this square. These description sets need not be finite even though every description and value interface is finite.

Change of description	Required data	What is established
Tree reification	A supported tree Token class.	Ordered child records and shared subterms; no evaluator is assumed.
Term compilation	Primitive term shape, interpretation and declared ports.	A valid graph with the term’s value.
Module expansion	A ranked library, fresh nodes and ordered port wiring.	A valid graph with the call’s denotation.
Region fusion	A valid region and its complete boundary interface.	A callable component with the same boundary behavior.
Online replacement	A consistent completed frontier and an equivalent residual implementation.	The original invocation’s remaining result is preserved.

Table 9: Relative atomicity requires an explicit construction at each level. The last row is proved in Section 10.10 ; it is not a consequence of packing alone.

Panel of Figure 8 — Figure 8: Coherence of changing frontier interfaces, in $\mathbf{FinSet}$ . Left: advancing in two stages equals advancing directly. Right: advancing the boundary and then finishing preserves the residual output. Commutativity holds for every input of $C_{U}$ , including boundary tuples not reachable from the original external input.

Panel of Figure 9 — Figure 9: Two levels of a certified sharing transformation. Above: an adjunction between completion lattices, not an inverse between graph descriptions. Below: state transfer is a commuting square in $\mathsf{TS}_{E}$ . The closure $q^{*}q_{!}$ adds source occurrences whose values are available from already completed shared nodes.

Panel of Figure 10 — Figure 10: Replacing unfinished work at a completed boundary, in $\mathbf{FinSet}$ . The left arrow summarizes values already obtained; the bottom arrow can use a new implementation of the same residual mapping. At runtime the boundary tuple is retained, so this square does not prescribe recomputation from the original input.

Description of $P_{n}$	XOR work	Span	Correctness certificate
Separate left-associated prefixes	$n(n-1)/2$	$n-1$	Direct term evaluation.
Shared prefix chain	$n-1$	$n-1$	Syntactic sharing Token map.
Recursive parallel prefixes	$w_{n}\leq 2n-2$	$\leq 2\lceil\log_{2}n\rceil$	Associativity and recursive construction.
Block family $R_{n,b}$ , $b\geq 2$	$(n-b)+w_{b}+n-\ell_{1}$	$\leq\lceil n/b\rceil+2\lceil\log_{2}b\rceil$	Local prefixes, totals and associative recombination.

Table 10: One behavior with several dependency structures. Work counts XOR operations; input delivery, output materialization, scheduling and communication are excluded. The bounds concern these constructions, not optimality over every implementation.

Panel of Figure 11 — Figure 11: Finite structural stages and their unbounded union. The displayed triangle is part of the full inclusion chain. Compatible finite-stage values determine the unique dashed Token map; no step evaluates the infinite union all at once. This diagram describes monotone structural growth or an append-only history, not arbitrary replacement of live configurations.

Panel of Figure 12 — Figure 12: A deterministic forward pass, with $\mathcal{F}_{\theta}=F_{L-1,\theta}\circ\cdots\circ F_{1,\theta}$ . $\mathcal{X}_{n}$ is the set of texts tokenized to length $n$ . Position information is supplied at the input or within the blocks according to the architecture. Each arrow after tokenization is a function on a whole sequence. Selected heaps turn particular arrows into Token maps; being a function alone does not specify which structure is preserved.

Panel of Figure 13 — Figure 13: Forgetting location, in $\mathbf{Set}$ . The dashed factorization exists exactly when the observation is constant on every coordinate fiber. Equal vectors do not by themselves establish that condition. These are observation functions; Token-map status additionally requires specified heaps.

Panel of Figure 14 — Figure 14: A coordinate comparison between located stages, in $\mathbf{Set}$ . With the same causal heaps transported to both stages, it is also a square of Token maps. The top arrow transports the same coordinates; it is distinct from the actual block update $\widehat{F}_{\ell,\theta}$ .

Panel of Figure 15 — Figure 15: Prefix causality as factorization in $\mathbf{Set}$ . The projection $\pi_{n,k}$ keeps the first $k$ coordinates. Theorem 11.5 is equivalent to existence of the lower map for every $1\leq k\leq n$ . The superscript records the fixed original length $n$ ; equality with a separately specified shorter-length model is the additional consistency condition of Section 11.6 .

LLM component or protocol	Representation in the framework	What the execution account permits
Heads and known-position operations	Independent subgraphs joined at explicit consumers	Concurrent scheduling subject to actual dependencies and resource limits.
Layer stack and generation loop	Composed maps and explicitly supplied next inputs	Waiting on real dependencies; no general elimination of layer or generated-token dependence.
Key–value cache	Invocation state tied to parameters, prefix and positions	Reuse under a proved consistency invariant; migration requires preservation of that state.
Kernel or representation choice	Alternative descriptions at a fixed interface	Certified exact substitution, or a separately quantified approximation.
Request length and worker availability	Interface family, active tasks and resource protocol	Distinct forms of elasticity, with their respective consistency and progress conditions.

Table 11: How the concurrent-machine proposal relates to the decoder model. These are formal correspondences and correctness conditions, not measured claims of faster LLM inference.

Explore similar work

Feb 15, 2026cs.LG

You Can Learn Tokenization End-to-End with Reinforcement Learning

Tokenization is a hardcoded compression step which remains in the training pipeline of Large Language Models (LLMs), despite a general trend towards architectures becoming increasingly end-to-end. Prior work has shown promising results at scale in bringing this compression step inside the LLMs' architecture with heuristics to draw token boundaries, and also attempts to learn these token boundaries with straight-through estimates, which treat the problem of drawing discrete token boundaries as a continuous one. We show that these token boundaries can instead be learned using score function estimates, which have tighter theoretical guarantees due to directly optimizing the problem of drawing discrete token boundaries to minimize loss. We observe that techniques from reinforcement learning, such as time discounting, are necessary to reduce the variance of this score function sufficiently to make it practicable. We demonstrate that the resultant method outperforms prior proposed straight-through estimates, both qualitatively and quantitatively at the

100

million parameter scale.

Sam Dauncey, Roger Wattenhofer

Department of Electrical Engineering, ETH Zurich, Zurich, Switzerland.

Tokenizer Uncertainty Score

Ask PDF

Dec 14, 2024cs.CL

Tokens, the oft-overlooked appetizer: Large language models, the distributional hypothesis, and meaning

Tokenization is a necessary component within the current architecture of many language mod-els, including the transformer-based large language models (LLMs) of Generative AI, yet its impact on the model's cognition is often overlooked. We argue that LLMs demonstrate that the Distributional Hypothesis (DH) is sufficient for reasonably human-like language performance (particularly with respect to inferential lexical competence), and that the emergence of human-meaningful linguistic units among tokens and current structural constraints motivate changes to existing, linguistically-agnostic tokenization techniques, particularly with respect to their roles as (1) vehicles for conveying salient distributional patterns from human language to the model and as (2) semantic primitives. We explore tokenizations from a BPE tokenizer; extant model vocabularies obtained from Hugging Face and tiktoken; and the information in exemplar token vectors as they move through the layers of a RoBERTa (large) model. Besides creating suboptimal semantic building blocks and obscuring the model's access to the necessary distributional patterns, we describe how tokens and pretraining can act as a backdoor for bias and other unwanted content, which current alignment practices may not remediate. Additionally, we relay evidence that the tokenization algorithm's objective function impacts the LLM's cognition, despite being arguably meaningfully insulated from the main system intelligence. Finally, we discuss implications for architectural choices, meaning construction, the primacy of language for thought, and LLM cognition. [First uploaded to arXiv in December, 2024.]

Julia Witte Zimmerman, Denis Hudon, Kathryn Cramer +9

Computational Story Lab, Vermont Complex Systems Institute, University of Vermont, Burlington, VT 05405, USA · Vermont Complex Systems Institute, University of Vermont, Burlington, VT 05405, USA · Department of Computer Science, St. Michael’s College, Colchester, VT 05439, USA +3

Single-Token Output Distributions Distributional Information Transformer Architectures Generative Artificial Intelligence

Ask PDF

Sep 23, 2026cs.CL

Distilling Sequential Computation in Transformer Language Models

Transformer language models process sequences token by token in an autoregressive manner, making growing contexts increasingly expensive. Yet many adjacent token spans are highly predictable or frequently occur as stable units, suggesting that their representations may be compressible. We introduce a method for distilling sequential computation by replacing spans of input tokens with collapsed representations, computed on the fly by a lightweight merge module. This module generates a single surrogate embedding from a sequence of static token embeddings that captures the functional role of the multiple tokens, allowing pretrained models to operate on compressed inputs without architectural changes or re-training. We apply this approach during inference to compress both prompts and intermediate decoding steps, using a rollback mechanism to substitute stored multi-token KV cache entries with their single-step surrogates. Experiments across diverse models show that the merge module can be used to reduce effective sequence length by up to 40% with minimal accuracy degradation across language modeling evaluations and downstream tasks, including question answering, summarization, commonsense reasoning, and long-form mathematical reasoning. Additional lightweight adaptation of the merge module further improves the accuracy-compression trade-off in selected settings. These results demonstrate that sequential token computation in Transformers can be effectively approximated through condensed surrogate representations that approximate the original behavior without model updating.

Zixuan Lan, Jessica Yang, Yanhong Li +2

The University of Chicago · Toyota Technological Institute at Chicago · Independent Researcher +1

Transformer Architectures Token Embeddings

Ask PDF