Token Space: A Category Theory Framework for AI Computations

Wuming Pan

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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}

.

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.

Token Space: A Category Theory Framework for AI Computations

Abstract

Figures & tables

Explore similar work

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

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

Distilling Sequential Computation in Transformer Language Models