Making deep learning perform real algorithms with Category Theory (Andrew Dudzik, Petar Velichkovich, Taco Cohen, Bruno Gavranović, Paul Lessard)

Language models cannot do addition. Not really. I keep seeing claims that they can, and every time I see this claim, I go back to ChatGPT and so on and check, and they can’t. What they can do is learn patterns, which work a lot of the time. But you can always trip them up by doing something like this: if you ask ChatGPT, “What is a bunch of eights plus a bunch of ones with a 2 at the end?” it will get the correct answer because it will recognize the trick.

It’ll say, “Ah, that’s just 1 and a bunch of 0s.” It’ll know that you’re trying to trick it. But if you change one of the eights to a 7, now it has to actually know what it’s doing. It has to walk up, hit the 7, and stop propagating 0s, and it simply fails. It either chokes and makes up some nonsense, or it says it’s 1 with a bunch of 0s anyway. It definitely can’t add in the basic way that we know how to do it algorithmically, the way humans learn.

And so, really teasing this apart on a very basic level, like Newton’s 3 laws of motion: has it encapsulated them? Whether that’s Veo or Genie, have these models encapsulated the physics of that 100% accurately? Right now, they’re not. They’re approximations, and they look realistic when you casually look at them. They’re not accurate enough yet to rely on for, say, robotics.

1. Models Need Intrinsic Computation

Just because we can achieve some level of moving the needle by hooking up a really potent tool to a language model doesn’t mean that we shouldn’t think about what the next generation of these models should look like and how we can make them intrinsically better. Even if you have the best tool in the world, that is not going to save you if you cannot predict the right inputs for that tool.

Even some of the current frontier models, as you probably know, will perform hundreds of billions of multiplications just to produce a single token of output, yet they cannot reliably multiply even relatively small numbers together without failing. This, to me, hints at a great misalignment between what we are training these systems to do and how we’re building them, and what we might want to use them for downstream, especially if we’re doing reasoning or science.

But it seems like, let’s say, an LLM, if you teach it properly, can do addition up to some failure of its memory, just like humans. We might forget a digit or forget to carry over, so we do the algorithm wrong sometimes with some probability. Up to that, it can learn this procedure of adding long-digit numbers.

Is it neural? Is it symbolic? It’s doing something, some algorithm, something symbolic perhaps. But it’s doing that with its neural machinery, and the neural machinery also allows it to, first of all, absorb tons and tons of world knowledge and deal with the vagueness of concepts—the fact that things don’t exactly fit your good old-fashioned AI symbolic theory most of the time.

We’ve all played with MCP servers. We know that we can hook tools up to these things. Why not just call a calculator? Andrew argues that tool use isn’t enough, right? We still need to be thinking about the actual architecture underneath. It still matters.

Internalizing things, I think, has a chance to be a lot more stable. The relationship between neural nets and tools is somewhat complicated. I think you can do a lot with it. You can do a lot of interesting search, but there are a few disadvantages.

One is that you may have to call the model a bunch of times because it may get an answer, but it may not be the answer it was expecting, so it might have to rethink things and go back. Imagine a situation where you had some complex reasoning problem where, along the way, you had to do a series of little additions. You had to say, “Okay, so then this, and then this, and then how many of these are there? Okay, and then how many of these?” It could be quite complicated to keep calling out to a tool, going back, calling out to a tool, and going back.

It seems like there are big efficiency gains if you’re able to equip the model itself to do certain kinds of basic computation or reasoning internally.

2. Geometric Symmetry Has Limits

Geometric deep learning was a pretty interesting episode, and certainly a very exciting period in my own research and what I’ve done together with the team. Already in that very first episode that we did together on geometric deep learning, there was a hint of a discussion about how geometric deep learning might not necessarily be enough. It may require us to broaden our lens on what we mean by geometric deep learning, and this is something we’re already very actively thinking about.

I think one of our co-authors, Taco Cohen, actually thought much more deeply about this. As I hinted at, groups, which are the bread and butter of geometric deep learning, might not be enough to capture the concept of aligning computation, which is my personal motivation.

For those who aren’t familiar, geometric deep learning fundamentally builds on the concept of constructing neural networks in a way that is what we call equivariant to symmetry transformations. What this means, in a nutshell, is that if I transform my input in some way, I should get predictable outputs from my neural network if that transformation is something that I find to be irrelevant.

One standard example is translations of images. If I have a picture of a cat and decide to shift it by a certain number of pixels, it’s still a picture of a cat. That hasn’t changed; I’ve just changed the way I’m looking at that cat. So I’d like to build my model to be what we call translation-equivariant, such that when I apply such a shift, I’ll still get the same output: that this is indeed a cat.

In a similar manner, graph machine learning, which is an area that I’m personally really passionate about, deals with extracting useful representations of graph-structured data, like molecules. Graphs have the inherent property that there are many different ways you can show them to the model, and typically you have to present them using some kind of adjacency matrix of nodes by nodes.

What happens if I decide to permute the order in which I show you those nodes? I permute the matrix’s rows and columns accordingly. This is still the same graph. I’d still want to get exactly the same outputs on that graph, right? So I can build into my models this notion of permutation equivariance, which guarantees that even if I permute my nodes, I’m still going to get predictable and basically identical outputs, up to permutation, for those permuted graphs.

This is a really important property because it reduces, almost exponentially, the amount of data you need to fit a system like that to a satisfactory level of behavior. It should come as no surprise that transformers, at their heart, are permutation-equivariant models. Once you’ve put token embeddings and position embeddings into tokens, you can permute them all you want. You’ll get exactly the same response.

If you wanted to learn that kind of symmetry with a simple MLP of tokens, that would’ve taken you exponentially more data than the trillions that we currently use to train these models, so likely data you wouldn’t be able to find.

We looked at geometric deep learning from a group-symmetry point of view, which is a very nice way to describe spatial regularities and spatial symmetries. But it’s not necessarily the best way to talk about invariance of generic computation, which you would find in algorithms.

I have input that satisfies certain preconditions. I want to say that once I push it through this function, it should satisfy certain postconditions. This is not the kind of thing we can very easily express using the language of group theory. However, it is something that perhaps we could express more nicely using the language of category theory.

I do think that some very high-level priors are probably a good idea and perhaps even necessary. In my PhD, I worked a lot on building knowledge about symmetries into neural networks. For many problems, knowledge about symmetries is something that, first of all, gives you a lot of bang for the buck.

We know from physics already, and now from empirical results in machine learning, that building these things into neural networks or putting a constraint on your physical theory based on symmetries gives you a lot of information, or really restricts the space of hypotheses. At the same time, it doesn’t bias your model if your problem indeed has this symmetry.

That’s the kind of thing we should be looking for: a very high-level, abstract prior. We’re not trying to encode, going back to the example I gave just now, the fact that light switches make lights go on. We can figure that out from data, from reading text on the internet at scale, from trial-and-error learning in an interactive environment.

Perhaps the fact that there’s space—3D space—and that your 2D images are a projection of that is a useful prior.

3. Category Theory Generalizes Symmetry

Category theory is very much in the eye of the beholder. I think, in the first instance, for me, categories are a very mundane thing from pure mathematics, where I come from. Category theory means studying categories for their own sake.

But everybody uses categories. The question is: what exactly are they? I really come from algebra, and a lot of my motivation comes from studying algebra. One way you can think about categories is algebra with colors.

For example, let's say we're multiplying square matrices. I can think of each square matrix as a little magnet, and I just hook them up together; they stick, and you get a bigger and bigger magnet, and everything makes sense. But now suppose I had special magnets that had colors on each side, and I could only connect them if the colors were the same. That sounds a bit weird, but it's exactly what happens with non-square matrices.

When we multiply two matrices, we have to follow a rule that they are not allowed to be multiplied unless the numbers match up. If I have an M-by-N matrix and I want to multiply on the left with an L-by-M matrix, I can do that because the Ms are the same, but otherwise I can't. There's a kind of color violation. So the point is a situation where we want to be able to compose things, to hook them up together, but we can't always do it. That's basically what categories are designed to cover, and I think the matrix example illustrates that they're not so mysterious. It's just when you want to be talking about, for example, many different-sized vector spaces at once, as you often do in neural networks because you have hybrid shapes with dimensions of different sizes and so on.

Petar Veličković

You end up wanting something where you take this partial compositionality into account.

I think this geometric deep learning blueprint that we described there can be generalized. Category theory made a lot of things click for me. I'm hoping, let's say, that it will allow us to generalize this methodology of geometric deep learning and equivariance to not just reason about symmetries, but far more general kinds of structures and structure-preserving maps.

Could it help there in the sense that we imbue the models with these geometrical priors, and we think these high-resolution priors describe the physical world that we're in? Could this category thinking allow us to somehow bring all of those together in some new way?

Well, you can certainly see how they're all instances of the same thing. Those things, once you learn them, start coming back everywhere. What's very nice about the category-theoretic way of thinking is that it's extremely systematic, and it tends to guide you in the right direction because the examples I've given you already show that, right? This notion of equivariance is something that someone thinking about groups and group representations and so on will come up with and find to be a very useful concept for mathematical reasoning.

But it falls out automatically if you already know category theory and you just define the categories of relevance here, define your group as a category, for example. Then you just follow the definitions. You say, “Well, okay, so what is a functor from my category to the category of sets?” For example, okay, it's a mapping like this. That gives you the definition of a group representation. And then you look at what is a natural transformation between such functors. You write out the definition. You find, “Oh, okay, it's an equivariant map in this case.”

And so it tends to produce meaningful definitions that domain experts in a mathematical domain will often have independently come up with. It's for lazy people or uncreative people. You don't have to be clever; you just have to follow the rules, and out come these very natural definitions and a kind of mathematics that just works very nicely. Everything fits together, just like with Lego pieces or something, right? They always fit exactly. Yeah, that allows you to build these elaborate mathematical structures that have nice properties.

There's a historical analogy worth keeping in mind. Before the periodic table, before we understood protons and electrons, practitioners of alchemy made real advances, but without a principled foundation. Deep learning today may be in a similar position. We have powerful empirical results, but we lack the fundamental theory that would let us derive new architectures rather than just stumbling upon them. Categorical deep learning is an attempt to find that periodic table for neural networks.

Deep learning, despite its remarkable success, is a field permeated by ad hoc design choices. Neural network architectures have all these knobs and tweaks that we can't formally justify just yet. There is no unifying framework for deep learning that would explain the probabilistic perspective, the neuroscience perspective, and the gradient-based iterative-updating perspective. In fact, in the future, we might look at deep learning very differently, and our claim is that category theory will become the unifying deep learning framework.

But you seem to be making the argument that the interpolative function space of neural networks can model algorithms more closely to real-world problems, potentially finding more efficient and pragmatic solutions than those classically proposed by computer scientists.

Petar Veličković

We are working in this high-dimensional space, which is not necessarily easily interpretable or composable because you have no easy way of saying, for example, in theoretical computer science, if you want to compose two algorithms, you're working with them in a very abstract space, which means that you can easily reason about stitching the output of one to the input of another, whereas you cannot make that easy of a claim about latent spaces of two neural networks, right?

Geometric deep learning is powerful, but it assumes all transformations are invertible. What happens when computation destroys information?

4. Algorithms Need Structural Guarantees

Petar Veličković

Strictly speaking, I wasn't planning to talk about any of that stuff at the time. It was very much work in progress and just trapped in my head as a collection of possible ideas, but not something I remotely knew how to execute on. But I was very passionate about algorithmic reasoning at the time as well. I still am, and I still believe that building machine learning models that are capable of aligning with classical computation is going to be really, really important to address the shortcomings that are not so easily plugged by just gathering a better dataset.

Fundamentally, some of these things are likely to be unable to generalize easily outside the distribution you've trained them on, and especially for reasoning problems, that is the case. When you think about all of the big scientific advances that have been made with large language models, for example, up to this date, I would argue that most of the ones I'm personally familiar with are a result of a careful combination of a large language model and an algorithmic procedure in the background that actually makes sure to give it robustness properties.

Think about things like FunSearch, AlphaCode, and AlphaGeometry. All of these systems have discovered new knowledge in computer science, in competitive programming, and even in geometry problems at the IMO. But in all cases, you've hooked up a language model to either a genetic algorithm, some clustering mechanism, or a theorem prover, all of which have very nice correctness guarantees. If you can run this model sufficiently many times to correct itself using the algorithm, you can end up with really nice solutions.

The problem with geometric deep learning is that, as I said, it talks about symmetry, so permutations or circular shifts. Those are generally things that have very specific and rigid behaviors. Typically, one of the things we assume about symmetries is that they are invertible. So basically, whenever I permute nodes, I can always permute them back. I haven't lost any information.

Usually with images, when we do shifts, we actually pad the image with zeros to make sure that no image data is lost and things like that. So basically, it always assumes that it's still the same input; we haven't lost any information. Now, why is this a problem for me, who is really interested in aligning models to classical algorithmic computation? Well, as any computer scientist will know, many programs you write will delete or destroy some of the data, so that it is no longer a symmetry. You cannot invert it.

Maybe one simple example, other than the naive example of taking a list and deleting half of its elements for no reason, is pathfinding. We talk a lot about algorithms like Dijkstra's or Bellman–Ford inside a computer science curriculum. In short, those are algorithms that, starting with a directed weighted graph, predict what the shortest-path lengths are inside that graph, right?

Now, the thing is, there are many, many different graphs with different weights that are going to have exactly the same shortest paths and potentially even the same shortest-path lengths. However, those graphs are different, and once you've applied Dijkstra's algorithm or Bellman–Ford's algorithm, you'll have lost the information contained in the graph in the final output of that algorithm, right? Many different graphs will be compressed to exactly the same output, right? So this is not an operation I can describe using a symmetry.

It took me a while to realize how we can be formal about this, how we can try to put some theory on it, and, even now down the line, how we can build some practical models using it. I was fortunate enough to start chatting with Andrew, who is my colleague at DeepMind and has a category theory background. He’s been thinking about some of these problems himself in the past.

It was a great match. Together with him, it was a long way, but we managed to gradually relax the constraints that a group gives us. We first looked at removing the invertibility part, which led us to monoids, and then we derived some interesting theory on asynchrony and variance in models using monoids.

We’re now also looking into removing the 2nd constraint of groups, which is the requirement that every single computation must compose with every other piece of computation. As you might also know from computer science, you cannot always do that. You must make the output of your 1st function match the input type of the 2nd one; otherwise, they can’t compose. So this leads us to categories, and that’s what led us to categorical deep learning.

Things like intentionality, planning, System 2, reasoning, and stuff like that—I think you’re placing the assumption that there’s something standard about that.

Petar Veličković

Mm-hmm. Yeah, exactly. To some extent, there is, because for a lot of these algorithms, we even have proofs that they will arrive at optimal solutions if you give them enough time and put them in the right context. I actually think it should be a synergy, right? As you said, with modern large-scale deep-learning systems, we actually stand a chance to map really complicated, noisy, real-world scenarios into a space where those algorithms might become applicable, right?

The main argument we’re perhaps trying to make here is that asking the model to both do that translation and robustly invoke the algorithm is likely a bit too much to ask because, among other things, there’s a fixed computational budget. That’s already one recipe for failure as inputs get larger because, as you know, multiplication, as I mentioned, is a problem for which we don’t really have a super-efficient algorithm yet. The best-known one is n log n, and that one relies on complicated number-theoretic constructions, let’s say.

So most people know just the n² quadratic algorithm for multiplication. The amount of resources that you need to reliably multiply 2 numbers will grow, sometimes superlinearly, based on the size of those 2 numbers. Currently, our systems can cope with that implicitly if you add things like chain of thought, which gives the model more thinking time, and so on. But fundamentally, all of those things are patches that might help for a particular class of problems but then fail somewhere else, just because of the nature of how complicated the entire space of computational problems is, right?

Basically, I believe in a future where the neural network will deal with the understanding of the world, with the translation of what’s happening in the world into some abstract space, which might just be high-dimensional embeddings, by the way. That’s also plausible. Then there will be some component that we have baked into the system, either through priors, very careful losses, or even through combining systems with tools, which has already proved really useful. That component will then execute the computation in a way that we can reason about.

I should stress that what I mean by reasoning is not 100 percent accuracy on every single input. I find that humans can reason, and humans are not 100 percent accurate on every single input you give them. As you can see, if you ask me to multiply 2 numbers that are 50 digits long, I will definitely make some mistakes.

The point is that I would like a system to understand the amount of effort that needs to go into doing some kind of computation and, at least, give me either an estimate of how likely it is to make mistakes or some notion of, “I’m sorry, the problem you’ve asked me to do is too computationally large for my capabilities. I would like to just back off and not answer,” right? Currently, systems are not trained to do that. They’re trained to always try to give you an answer, which is very different from that.

Basically, I’m fine with making mistakes, but I would really like some awareness of when mistakes might happen and how big they will be. When you apply algorithms, you often have that. You can have correctness guarantees as well as convergence guarantees and things like that.

But you’re probably thinking, “Why do we need to use such abstract mathematics in the first place?” This kind of structured thinking can actually help us see what actually matters.

5. Abstract Mathematics Defines Structure

To introduce the notion of structuralist mathematics—and the best-known example of structuralist mathematics, category theory—I would like to begin with the distinction between analytic mathematics and synthetic mathematics. The usual 2 examples given for this are the geometry of Descartes versus the geometry of Euclid. For Descartes, lines are solution sets to equations, whereas for Euclid, lines are precisely that which is stretched out between 2 points.

What’s the essential distinction here? In analytic mathematics, stuff is made of stuff, right? There’s always some question of: I have to have some common foundation from which everything is built, and all of my lemmas, theorems, et cetera—everything eventually boils down to a computation in that more basic substance. On the other hand, in synthetic mathematics, I don’t need to know what the inside of a line is. That doesn’t matter.

The point is, I abstract only the principles by which I can make inferences about lines and their relationships to each other, right? The point is, you get rid of everything that is inaccessible to your logic, right? You get rid of all of this stuff that you might call detail, but it’s not even detail. It’s noise, because it doesn’t have any content for that which you can know, right? Therefore, it’s completely irrelevant.

Synthetic mathematics gets rid of all of that and focuses just on how you can produce more knowledge, right? To explain what I mean by structuralist mathematics, I want a synthetic mathematics of structure, right? What is structure?

In the context of machine learning, we’ve got lots of notions. Everyone says “structure,” right? The best-known and best-studied example of that structure is group actions, right? All of geometric deep learning is about group actions. But that’s only 1—it’s 1 pinprick in the vast, right? That’s just 1 thing, right?

There are lots of other things that come from theoretical computer science: the notion of things being lists or things being trees, all of these other various algebraic structures. You want a single language in which all of these various kinds of structure can be described elegantly. This is exactly why we appeal to category theory.

6. Higher Categories Share Weights

In the simplest possible terms, what do you mean by a 2-category?

Right. So if we talk about a category as a collection of things and relationships between them, these relationships are encoded as something we call morphisms. These are like generalized functions. They’re just arrows. We draw them as arrows.

Before we go any further, let’s ground what weight tying actually means. Imagine an RNN processing a sentence word by word, and at every time step, it uses the same neural network cell—the same weights—to process each word. That is weight tying, right? Forcing multiple parts of a computation to share identical parameters.

In traditional machine learning, we do just this, right? We code it up, but there’s no formal theory explaining when this is valid or what structure it preserves. I know it sounds abstract, but it just means that we can prove when weight tying is correct and derive new architectures where weight tying is guaranteed to preserve the structure that we actually care about.

But often, if we focus on 2 objects and look at all the maps between them—all these morphisms—these form a set in a category. There’s a set of morphisms. But now, if you take the ethos of category theory and don’t just have a set of things, but try to relate that set with some ways between them—if you look at this set of morphisms between 2 objects and start describing the ways these morphisms could be related, the properties they need to satisfy, which also involve some kind of composition, then we start getting at the notion of a 2-category: objects, morphisms, but also 2-morphisms as ways of relating them.

Category theory talks about these relationships between objects, as morphisms. But what about relationships between the morphisms?

Right. So these are what we call 2-morphisms or 2-cells, and these are the things we use to model some aspects of neural networks that we deem important. We shouldn’t just think of them as categories. They’re not just maps; they have this higher structure. We can think of them that way, certainly, but that doesn’t encode a lot of the interesting things we want to have about them.

And this is, I think, the idea of higher categories: you start modeling something with categories, and you realize, “Ah, well, all along I have been forgetting about this other important thing.” So you start putting more stuff into your theory while still trying to make it consistent.

The particular way we encode these higher morphisms, or what we use them for, I think the most important thing is weight sharing. So we get a comprehensive theory of how to do weight sharing in a way that’s not particularly tied to smooth spaces or vector spaces. It’s one that works for manifolds. It’s also one that my collaborators and I have used in my PhD to connect to game theory, where we talk about economic agents that have some strategies, and if we want 2 agents to operate with the same strategy, we do weight sharing there.

There are all these different fields where you can specify what these are, and the level of abstraction of a 2-cell is the one which really gets to the essence of that without having any specificity about the kind of thing you’re studying built in.

You could presumably just go to the 3rd order and to the 4th order. I mean, even with self-attention transformers, they model these 2-tuples, which is like a first-order relationship, but you could have 3rd-order, 4th-order, and so on. Are 2-morphisms enough, or should we go deeper than that?

Well, depending on who you ask, you’ll get very opinionated answers. When I started learning category theory, I was like, “Well, I’m never gonna go to 2-categories. That seems complicated.” Now I say I’m never gonna go higher than 2-categories because that seems too complicated. But people do 3-categories, infinity-categories, and you can really start building up these relationships higher and higher and get this really comprehensive theory that becomes a very different beast in some ways.

There is a school of thought that our brain works in this way. So we think using these symbols and these categories and so on, and then there’s the notion that the universe is a certain way, and we understand the universe with that kind of interface. So it’s almost like the driver for this is, “Here’s an interface. Here’s how we think. Here’s how the universe works. Let’s program computers in that way.”

That’s a big question. What happens with these things is that when we start adding more levels, more is different, and that’s the thing we start seeing in higher categories. When we add different kinds of relationships and morphisms, you start seeing these things that can be perhaps more aptly described as emergent effects. If you have 2 things and you want to study their behavior as a composite, you can either study their behavior individually and look at the joint behavior, or you can compose the systems and look at the behavior of the composite.

Yeah.

What we often found is these are not the same. In many compositional cases, these are isomorphic, but often there is a map going one way but not the other. So you have to start tracking this. Since this isn’t an equality anymore, you have to start tracking this higher cell. But now this itself might be a part of another system that gives rise to this plethora of levels and levels of emergent effects.

That’s one of the problems with higher category theory: it’s just so hard for us, with the complexity of our minds, to do this. So it’s certainly an open question what the best substrate is and how to encode these things, and people have done a lot of work in programming language theory on encoding not just data structures and algorithms, but type theories in which these algorithms are hosted in some categorical way.

People who believe in strong emergence think that there is no reductionism, but even with basic weak emergence, the analytical shortcut between the theories at different scales is computationally intractable. It’s very difficult to go between them. But we want to have some kind of theoretical framework that captures the whole thing, right? It captures the emergent organization as well as what’s going on underneath.

This is one of the goals of category theory: to find some fundamental abstractions that give rise to these very simple principles. Often when you look at some systems or some phenomena, it’s very complicated. But if you’re lucky enough, and if you set up good foundations, it’s always, “Oh, wait, it was very simple all along. I looked at it the wrong way.” So I don’t know where this could go, but we are certainly striving to make things as compositional as they could be.

In many of these fields where we have plenty of experimental evidence and a lack of good theories, category theory has a very good vantage point and just a lot of practical benefit: let’s stop and see what the good vantage point here is.

Do 2-morphisms allow us to think about weight tying?

Absolutely. If we think about a parametric morphism, it’s a map from A to B with a parameter p. We often want to change the parameter space. We often want to say, “Do the weight tying,” which, in practice, means we start from a smaller weight space and copy the weights in particular.

A 2-morphism in the 2-category of parametric functions is a reparameterization. So it’s a map between 2 parametric morphisms that is somehow coherent. There are some diagrams that have to be satisfied, but essentially they encode that one is obtained by precomposing with some form of weight tying. But it doesn’t have to be just copying. That’s the thing we’re finding out. It can be arbitrary relationships within the weights.

So one of the things that these 2-cells and 2-morphisms allow us is to see this algebraic structure encoded as relationships between the weights. And that goes back to what category theory is about: it’s about finding relationships between objects. So, absolutely.

7. Neural Networks Learn To Carry

So here’s the key connection to programming. In functional languages, we define data types like lists recursively. A list is either empty or it’s an element followed by another list. Categorically, this is an algebra for an endofunctor. The structure map of the algebra packages together all of the constructors of the data type, and the homomorphism from this algebra is exactly what programmers call a fold, a function that consumes the list by recursively applying some operation. So the framework is describing the very structure of recursive computation.

When you write code, you encounter syntax errors. You don’t so much encounter semantic errors. So the syntax is really quite grounded in the things that you’re actually typing in when you’re writing something, whether it’s an ordinary algorithm, a network architecture, et cetera.

The semantics is much more about how programs can behave. One example of this is list types. Lists are defined by a type constructor. Given a type T, you have another type, list of T. So what are the semantics of lists? Well, the semantics of lists are really things that are foldable, sort of foldable types. Numbers with addition are a sort of foldable type. If I have a list of numbers, I can just add them to sort of remove the list.

Now these foldable types, mathematicians have a very different name for them: monoids, which are a more general kind of group. But in any case, that’s sort of the semantics of lists. And before I say something about syntax, let me say that our paper is really mostly exploring things from the semantic angle.

Why is this? It’s because 2 different syntaxes can describe the same thing very easily. We could have an arithmetic theory where we have addition and we also have negation, or we could instead have subtraction. And you can describe the same things in those 2 different languages, but the languages really are different. They give you the same semantics, but the syntaxes are different.

And so when doing mathematical analysis, when proving theorems, it’s often really beneficial to work from a semantic point of view. But it’s worth really emphasizing that if you want to compare this work to some other work that’s done on equivariance and so on, that work is often being done from a syntactic angle.

So let’s pause to state the central claim of categorical deep learning. The proposal is basically that a neural network layer should be viewed as a homomorphism between 2 algebras for the same endofunctor. The endofunctor describes the kind of computation a network needs to respect, be it a group action, a list fold, or an automaton transition. And the algebras describe how that computation transforms the specific data. The homomorphism is then a function that maps between these 2 data representations while preserving the computational structure. When this homomorphism is a group action, you recover geometric deep learning, but the framework itself is far more general.

So what is the syntax, for example, of the action of a group? You say, “I want to think that I have one kind of thing, and then each group element takes that thing and sends it back to itself.”

So I have a single type, and then each group action does something to that type. I might have some points in the plane, and my group might be rotations and reflections that move those points around, but I’m still in the plane. But it turns out that this one-sorted syntax isn’t enough to even capture basic type constructors in computer science. So, for example, lists—you cannot deal with the syntax of lists using just a single sort. You need a multisorted syntax.

So the way that you can do this is to think of having 0-tuples, 1-tuples, 2-tuples, and so on. Given a k-tuple, I might be able to make some other kind of tuple, an l-tuple, by taking elements of my k-tuple and making them into some lists—l lists, right? That’s a syntax in the same way that group elements were a syntax, and it does have compositionality. If I have a way of packing things from a tuple into a bunch of lists, then I can pack those lists into other tuples of lists. But it’s clear that this is, first of all, many-sorted, and then also differs from the group case because all of this is highly non-invertible, right?

You can’t, by packing things more and more and more into lists, eventually undo the lists, right? You just get more lists. But we basically construct a model for the syntax. In the case of groups, a model in sets means a set acted on by the group, while, for example, a model in vector spaces would mean a vector representation of the group. Whereas in the case of the syntax for lists, you just get what I was calling before foldable types or monoids, things that are able to perform these syntactic operations in the expected way.

There’s just something where the mathematical reasoning works better if you expand your universe of objects a little bit, even if you only care about the original objects. This is a lesson that mathematicians have learned many times, and it’s why a lot of people will prefer to work on the semantic side, at least in the first instance. It turns out that there’s something very, very basic in mathematics that we all learned in elementary school that has been overlooked in the design of GNNs. And that’s the notion of a carry.

So what exactly is a carry? Well, suppose that I am able to implement a device, a number wheel, that can do arithmetic modulo 10, from 0 through 9. And now I want to build a kind of composite wheel that can do arithmetic modulo 100. So what do I need to do? I need this little mechanism such that when the wheel goes from 9 to 0, it turns the next wheel by 1. This is very simple, but it’s extremely at odds with the way that GNNs have been conceived of in the past.

In the past, generally, you send the whole state, but there’s no information in the state. The information is only in the change of the state. But it’s even worse than that. Even if you sent the change in the state, that’s not enough information. Because if I went from 9 to 0, is it because I added 1? Is it because I added 11? Is it because I subtracted 9? It turns out that it’s quite subtle to get this kind of thing to work in the presence of gradient descent.

It is a very fundamental aspect of how we assemble more complicated computational operations from simpler ones. One of the first things that you do if you’re describing a CPU is describe an adder. This is already something that we’re struggling to do in GNN terms. It turns out that this behavior is easy to get when you do discrete mathematics and very complicated to get when you do continuous mathematics. You can easily give this number wheel example. Everybody understands it because they know how to do addition. But getting it to happen in a way such that everything is continuous turns out to be really interesting.

The simplest examples of this phenomenon don’t occur until you’re dealing with 3-dimensional manifolds. So you would need to be thinking about things in 4-dimensional space. The simplest example that we know of is the so-called Hopf fibration. This is a situation where you can decompose a 3-dimensional sphere, so that’s a sphere in 4 dimensions. You can project it onto a 2-dimensional sphere so that all of the preimages are 1-dimensional spheres, or circles.

The 3-dimensional sphere is very different from the product of the 1- and 2-dimensional spheres, just the same way that Z mod 100 is very different from the product of Z mod 10 with Z mod 10. And so, something that I’m personally very excited about right now, coming out of this asynchrony work, is whether there are ways to exploit this type of geometric subtlety to create the phenomenon of carrying, properly model this aspect of algorithmic reasoning, and start to build actual CPUs in neural networks.

So their claim is quite straightforward at the end of the day. Deep learning has two languages, constraints and implementation, and we lack a single framework that cleanly links them together. Categorical deep learning produces the bridge, right, using a universal algebra in a two category of parametric maps. It recovers geometric deep learning as a special case while naturally expressing things like recursion, weight tying, and non-invertible computation. Now, if you want the formal story, go and read their paper. The link is in the description, especially the sections on para, weight tying, and recovering geometric deep learning. Cool. Thanks for watching.