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

We often think of Large Language Models (LLMs) as all-knowing, but as the team reveals, they still struggle with the logic of a second-grader. Why can’t ChatGPT reliably add large numbers? Why does it "hallucinate" the laws of physics? The answer lies in the architecture. This episode explores how *Category Theory* —an ultra-abstract branch of mathematics—could provide the "Periodic Table" for neural networks, turning the "alchemy" of modern AI into a rigorous science. In this deep-dive exploration, *Andrew Dudzik*, *Petar Velichkovich*, *Taco Cohen*, *Bruno Gavranović*, and *Paul Lessard* join host *Tim Scarfe* to discuss the fundamental limitations of today’s AI and the radical mathematical framework that might fix them. TRANSCRIPT: https://app.rescript.info/public/share/LMreunA-BUpgP-2AkuEvxA7BAFuA-VJNAp2Ut4MkMWk --- Key Insights in This Episode: * *The "Addition" Problem:* *Andrew Dudzik* explains why LLMs don't actually "know" math—they just recognize patterns. When you change a single digit in a long string of numbers, the pattern breaks because the model lacks the internal "machinery" to perform a simple carry operation. * *Beyond Alchemy:* deep learning is currently in its "alchemy" phase—we have powerful results, but we lack a unifying theory. Category Theory is proposed as the framework to move AI from trial-and-error to principled engineering. [00:13:49] * *Algebra with Colors:* To make Category Theory accessible, the guests use brilliant analogies—like thinking of matrices as *magnets with colors* that only snap together when the types match. This "partial compositionality" is the secret to building more complex internal reasoning. [00:09:17] * *Synthetic vs. Analytic Math:* *Paul Lessard* breaks down the philosophical shift needed in AI research: moving from "Analytic" math (what things are made of) to "Synthetic" math [00:23:41] --- Why This Matters for AGI If we want AI to solve the world's hardest scientific problems, it can't just be a "stochastic parrot." It needs to internalize the rules of logic and computation. By imbuing neural networks with categorical priors, researchers are attempting to build a future where AI doesn't just predict the next word—it understands the underlying structure of the universe. --- TIMESTAMPS: 00:00:00 The Failure of LLM Addition & Physics 00:01:26 Tool Use vs Intrinsic Model Quality 00:03:07 Efficiency Gains via Internalization 00:04:28 Geometric Deep Learning & Equivariance 00:07:05 Limitations of Group Theory 00:09:17 Category Theory: Algebra with Colors 00:11:25 The Systematic Guide of Lego-like Math 00:13:49 The Alchemy Analogy & Unifying Theory 00:15:33 Information Destruction & Reasoning 00:18:00 Pathfinding & Monoids in Computation 00:20:15 System 2 Reasoning & Error Awareness 00:23:31 Analytic vs Synthetic Mathematics 00:25:52 Morphisms & Weight Tying Basics 00:26:48 2-Categories & Weight Sharing Theory 00:28:55 Higher Categories & Emergence 00:31:41 Compositionality & Recursive Folds 00:34:05 Syntax vs Semantics in Network Design 00:36:14 Homomorphisms & Multi-Sorted Syntax 00:39:30 The Carrying Problem & Hopf Fibrations Petar Veličković (GDM) https://petar-v.com/ Paul Lessard https://www.linkedin.com/in/paul-roy-lessard/ Bruno Gavranović https://www.brunogavranovic.com/ Andrew Dudzik (GDM) https://www.linkedin.com/in/andrew-dudzik-222789142/ --- REFERENCES: Model: [00:01:05] Veo https://deepmind.google/models/veo/ [00:01:10] Genie https://deepmind.google/blog/genie-3-a-new-frontier-for-world-models/ Paper: [00:04:30] Geometric Deep Learning Blueprint https://arxiv.org/abs/2104.13478 https://www.youtube.com/watch?v=bIZB1hIJ4u8 [00:16:45] AlphaGeometry https://arxiv.org/abs/2401.08312 [00:16:55] AlphaCode https://arxiv.org/abs/2203.07814 [00:17:05] FunSearch https://www.nature.com/articles/s41586-023-06924-6 [00:37:00] Attention Is All You Need https://arxiv.org/abs/1706.03762 [00:43:00] Categorical Deep Learning https://arxiv.org/abs/2402.15332

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Speaker 00

  Language models cannot do addition. Um, not really. I keep seeing claims that they can, and every time I see this claim, I go again to ChatGPT and so on and check, and they can't. And uh, 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, okay, so. If you ask ChatGPT, what is a bunch of eights plus a bunch of ones with a two at the end? It will get the correct answer because it will recognize the trick. It'll say, ah, that's just one and a bunch of zeros. It'll know that you're trying to trick it. But if now you change one of the eights to a seven, now it has to actually know what it's doing. It has to actually sort of walk up, hit the seven,

• 0:43Speaker 00

  and stop sort of propagating zeros, and it simply fails. It uh, it either chokes and makes up some nonsense, or it says it's one with a bunch of zeros anyway. Like, it definitely can't add in the, in the, the basic way that, that we know how to do algorithmically that humans learn.

• 1:02Speaker 01

  And so like really teasing apart on a very basic uh, level like Newton's three laws of motion. Has it encapsulated it? Um, whether that's Vio or Genie, have these models encapsulated the physics of that a hundred percent accurately? And right now they're not, they're kind of approximations, and they look um, realistic when you just casually look at them. They're not uh, accurate enough yet to rely on for, say, robotics.

• 1:26Speaker 02

  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 would the next generation of these models look like? And how can we make them intrinsically better? Because 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, uh, they will, as you probably know, 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, right? So this is something that to me hints at a great misalignment between.

• 2:10Speaker 02

  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 if we're doing science.

• 2:19Speaker 03

  But it seems like, let's say, in L L M, if you teach it properly, you can just teach it to do, let's say, addition up to some failure of its memory, just like with humans. We might forget a digit or we forget to carry over. Or so, you know, we do the algorithm wrong sometimes with some probability. Up to that, it can learn this this procedure of adding long digit numbers. You know, 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, right? The fact that that things don't exactly want to fit

• 3:04Speaker 03

  your good old fashioned AI symbolic theory most of the time.

• 3:07Tim Scarfe?

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

• 3:21Speaker 00

  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 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. Like, imagine a situation where you had some complex reasoning problem, where along the way you had to do a series of little additions. You just had to sort of, okay, so then this and then this. And then, oh, how many of these are there? Okay. And then how many of these and so on?

• 4:04Speaker 00

  And you, it could be quite complicated to kind of keep calling out to a tool and then going back and then calling out to a tool and then going back. And, you know, it seems.

• 4:16Speaker 00

  Like there are big efficiency gains if you're able to equip the model itself to just do certain kinds of basic computation or reasoning internally.

• 4:26Speaker 02

  So yeah, 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 with geometric deep learning, there was a hint of discussion about how geometric deep learning might not necessarily be enough. It will require us potentially 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, Takoko, and actually thought much more deeply about this. Like I hinted at the fact that groups, which are the bread and butter of geometric deep learning,

• 5:06Speaker 02

  might not be enough for fitting the concept of aligning the computation, which is my personal motivation, right? So for those who are not familiar, geometric deep learning fundamentally builds itself on the concept of constructing neural networks in a way that is what we call equivariant to symmetry transformations. So what this means in a nutshell is if I transform my input in some way, I should get predictable outputs with my neural network if that transformation is something that I find to be irrelevant. One standard example is translations of images. So if I have a picture of a cat and I decide to shift it by a certain number of pixels, it is still a picture of a cat that hasn't changed. I've just changed the way I'm looking at that cat.

• 5:51Speaker 02

  So I would like to build my model to be what we call translation equivariant, such that when I do apply such a shift, I will 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. But graphs have this inherent property that there's many different ways you can show them to the model. And typically you have to present them using some kind of, say, adjacency matrix of nodes by nodes. But what happens if I decide to permute the order in which? I show you those nodes. So I permute the matrix's rows and columns accordingly. This is still the same graph. I would still want to get exactly the same outputs on that graph, right?

• 6:36Speaker 02

  So I can build into my models this notion of permutation equivalence, which guarantees that even if I permute my nodes, I'm still going to get predictable outputs and basically identical outputs up to permutation for those permuted graphs. And this is a really important property because it reduces almost exponentially basically the amount of data you need to fit a system like that to a satisfactory amount of behavior. And it should come as no surprise that transformers, at their heart, are permutation equivalent models. Once you've put token embeddings, 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 have taken you exponentially more data

• 7:20Speaker 02

  than the trillions that we currently use to train these models, so likely a 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, say, invariance of generic computation, which you would find in algorithms, right? It's like I have input that satisfies certain preconditions. I want to say something about, once I push it through this function, it should satisfy certain post-conditions. 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.

• 8:00Speaker 03

  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. And I think for many problems, you know, 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. And at the same time, it doesn't bias your model if indeed your problem has this symmetry.

• 8:45Speaker 03

  So I think that that that's the kind of thing we should be be looking for. This kind of very high level abstract prior, not trying to encode, you know, coming back to the example I gave just now, the fact that light switches make lights go on, that we can figure 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 is space, like 3D space, and that your 2D images are a projection of that, maybe that that is a useful prior.

• 9:16Speaker 00

  Category theory is very much in the eye of the beholder. I think in the first instance, for me, category theory, categories are a very mundane thing from pure mathematics where I come from. And category theory means, you know, when you study categories for their own sake. But everybody uses categories. The question is, what exactly are they? And I really come from algebra and a lot of my motivation comes from studying algebra. And one way you can think about categories is algebra with colors. So, you know, we can imagine sort of typical algebra. So for example, let's say we're multiplying square matrices.

• 9:58Speaker 00

  I can sort of think of each square matrix as a little magnet. And I just sort of hook them up together and they just stick and you kind of, you know, you get a bigger and bigger magnet and 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. And that sounds a bit weird, but it's exactly what happens with non-square matrices. When we multiply two matrices, we 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 M's are the same. But otherwise, I I can't. There's a kind of color violation.

• 10:43Speaker 00

  So the point is a situation where we want to be able to compose things, to 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 the matrix example illustrates 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 sort of hybrid shapes with, you know, dimensions of of different sizes and so on. You end up you end up wanting something where you take this sort of partial compositionality into account.

• 11:25Speaker 03

  I think this this geometric deep learning blueprint that we described there can be generalized. Yeah, category theory made a lot of things click for me. Or 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.

• 11:50Tim Scarfe?

  Could it help there in the sense that, you know, 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?

• 12:05Speaker 03

  Well, you can certainly see how they're all instances of the same thing. So those those things, once you learn them, they start coming back everywhere. And 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, well, the examples I've given you already show that, right? This this notion of equivariance, that's 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 it falls out automatically if you if you already know category theory and you just define the categories of relevance here, define your group as a category, for example.

• 12:50Speaker 03

  Then you just follow the definitions. You say, okay, so what is a funter from my category to the category of sets, for example? Okay, it's it's mapping like this. That that gives you the definition of a group representation. And then you look at. What is a natural transformation between such vectors? You write out the definition, you find, okay, it's an equivariant map in this case. And so it tends to produce meaningful definitions that domain experts, like in a mathematical domain, will have independently come up with very often. And so it's for lazy people who don't wanna, or uncreative people. You know, you don't have to be clever. You just have to follow the rules and be very systematic.

• 13:32Speaker 03

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

• 13:49Tim Scarfe?

  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.

• 14:18Speaker 05

  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. There is no unifying framework that would explain the probabilistic perspective, the neuroscience perspective, and merely just 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.

• 14:55Tim Scarfe?

  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.

• 15:07Speaker 02

  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?

• 15:33Tim Scarfe?

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

• 15:43Speaker 02

  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 kind of trapped in my head as a collection of possible ideas, but not something I remotely knew how to execute on, right? But I was very passionate about algorithmic reasoning at the time as well, I still am. And I still believe that like building machine learning models that are capable to align to classical computation is going to be really, really important to address the shortcomings that are not so easily plugged by just gathering a better data set. Like fundamentally, some of these things are likely to be restricted to not be able to easily generalize outside of the distribution you've trained them on. And especially for reasoning problems, that is the case.

• 16:26Speaker 02

  When you think about all of the big scientific advances that were done with large language models, for example, up to this date, I would argue 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, which actually makes sure to give it robustness properties. So think about things like FunSearch, like AlphaCode, like AlphaGeometry. All of these systems have discovered new knowledge in computer science, in competitive programming, in even geometry problems at the IMO. But in all cases, you've hooked up a language model to either a genetic algorithm or some clustering mechanism or a tier improver, which all have very nice correctness guarantees,

• 17:12Speaker 02

  which then, if you can run this model for sufficiently many times to kind of 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 symmetries. So permutations or circular shifts, those are generally things that have very specific and rigid behaviors. And typically, one of the things we assume about symmetries is that they are invertible. So basically, that whenever I permute nodes, I can always permute them back. I haven't lost any information. And 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.

• 17:54Speaker 02

  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 some of the data or destroy some of the data. So that is no longer a symmetry. You cannot invert it. Maybe one simple example is, other than just the naive example of I'm going to take a list and delete half of its elements for no reason. Let's start with pathfinding. So we talk a lot about algorithms like Dijkstra, Bellman-Ford inside a computer science curriculum. In short, those are algorithms that, starting with a directed weighted graph, predict what are the shortest paths lengths inside that graph, right?

• 18:34Speaker 02

  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 the transformations of Dijkstra's algorithm or Bellman-Ford algorithm, you'll have lost the information that is contained about the graph in the final output of that algorithm, right? Because many different graphs will be compressed to exactly the same output, right? So this is not an operation I can describe using a symmetry. And then this journey gradually, like it took me a while to realize how we can be formal about this, how can we try to put some theory on this, and even now down the line, how can we build some practical models using this?

• 19:18Speaker 02

  And I was fortunate enough to start chatting with Andrew, who is my colleague at DeepMind, who has a category theory background, and he's been thinking himself about some of these problems in the past. So It was a great match because together with him, it was a long way, but we managed to gradually relax the constraints of what a group is giving us. We first looked at removing the invertibility part, which led us to monoids, and then we derived some interesting theory and asynchronous invariance in models using monoids. And now we're also looking into removing the second constraint of groups, which is the requirement that every single computation must compose with every other piece of computation. As you might also know

• 20:00Speaker 02

  in computer science, you cannot always do that. You must make the output of your first function match the input type of the second one. Otherwise, they can't compose. So this now leads us to categories and, well, that's what led us now to categorical deep learning.

• 20:14Tim Scarfe?

  Things like intentionality and planning and system two and reasoning and stuff like that. I think you're placing the assumption that there's something standard about that.

• 20:23Speaker 02

  Yeah, exactly. I mean, and to some extent, there is because for a lot of these algorithms, we have even proofs that they will arrive at optimal solutions if you give them enough time and put them in the right context. And I actually think it's gonna, it should be a synergy, right? Because 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? Now, the main argument that maybe we are trying to make in some part here is that asking the model to both do that translation and robustly invoke the algorithm is likely a bit too much to ask

• 21:06Speaker 02

  because, among other things, you've said fixed computational budget. That's already one recipe for failure as inputs get larger because, as you know, for example, multiplication, as I mentioned, is an algorithm which 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 like complicated number theoretic constructions, let's say. So most people know just the N-squared quadratic algorithm for multiplication. So the amount of resources that you need to reliably multiply two numbers will grow. And sometimes super linearly, based on the size of those two numbers. And 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.

• 21:50Speaker 02

  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? So 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. And then there will be some component that we have baked into the system, either through priors or through very careful losses, or even through combining systems with tools, which has already proved really, really useful, that will actually then execute that computation in a way that we can reason about it. And I should stress, by the way, what I mean by reasoning is not 100% accuracy on every single inputs.

• 22:34Speaker 02

  I find that humans can reason and humans are not 100% accurate on every single input you give to them. Right? As you can see, if you ask me to multiply two numbers that are like 50 digits long, I will definitely make some failures if you ask me to do that. But you know, the point is that like, what I would like is that a system understands the amount of effort that needs to go into doing some kind of computation. And maybe at least to give me some, either an estimate of how likely it is to make mistakes, or some notion, even 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, right? Which is very different to that.

• 23:17Speaker 02

  So 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, which when you apply algorithms, you often have that. So you can have correctness guarantees as well as, you know, convergence guarantees and things like that.

• 23:31Tim Scarfe?

  But you're probably thinking, why do we need to use such abstract mathematics in the first place? Well, this kind of structured thinking can actually help us see what actually matters.

• 23:41Speaker 06

  To introduce the notion of structuralist mathematics, and then the best known example of structuralist mathematics, category theory, I would like to begin. With the distinction between analytic mathematics and synthetic mathematics. And the usual two examples that are given for this is 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 two points. What's the essential distinction here? In analytic mathematics, stuff is made of stuff, right? There's always some question of, okay, I have to have some common foundation from

• 24:23Speaker 06

  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, it's like, I don't need to go, I don't need to know what like the inside of a line is, that doesn't matter. The point is, I only abstract what are the principles by which I can make inference on lines and their relationships to each other, right? The point is, you get rid of everything that is inaccessible to your logic, right? So you get rid of all of this stuff that you might call detail, but it's not even detail, it's noise, it does, because it doesn't have any content for that which you can know, right? And so therefore, it's completely irrelevant. So synthetic mathematics gets rid of all of that and focuses just on how you can produce

• 25:08Speaker 06

  more knowledge, right? And so then, to explain at least what I mean by a structuralist mathematics, I want a synthetic mathematics of structure, right? What is structure? You know, in the context of machine learning, we've got lots of notion, 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 one, that's like one pinprick in the vault, right? That's just like one thing, right? There are lots of other things, say, that come from theoretical computer science, the notion of things being lists, or, you know, things being trees, all of these other various like algebraic structures. So you want like a single, you know, language in which all of these various kinds of structure can be described elegantly. This is exactly why we appeal to category theory.

• 25:52Tim Scarfe?

  In the simplest possible terms, what do you mean by two category?

• 25:55Speaker 06

  Right, right. So.

• 25:57Speaker 07

  If we talked about a category as a collection of things and relationships between them, these relationships are encoded as something we call morphisms. So these are like generalized functions. These are just arrows. We draw them as arrows.

• 26:10Tim Scarfe?

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

• 26:48Speaker 07

  But often, if we focus on two objects and look at all the maps between them, all these morphisms, so these are a set in a category, there's a set of morphisms. But now if you take the ethos of category theory and not just have a set of things, but we try to relate that set with some ways between them. If you look at this set of morphisms between two objects now, if we add the notion or start describing the ways these morphisms could be related, the properties they need to satisfy, which is also some kind of composition, then we get, start getting at the notion of a two-category, which is objects, morphisms, but two-morphisms as ways of relating them.

• 27:25Tim Scarfe?

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

• 27:34Speaker 07

  Right, right. So these are these that we call two-morphisms or two-cells. And these are the things we use to model some aspects of neural networks that we deem are important. We shouldn't just think of them as categories. They're not just maps, but they have this high, we can think of them certainly like this, but that... That does not encode a lot of the interesting things we want to have about them. And this is, I think, the idea of higher categories, where you start modeling something with purely 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. And the particular way we encode these higher morphisms, or what we use them for, I think the most important thing is weight sharing.

• 28:16Speaker 07

  So we get a comprehensive theory of how to do weight sharing in a way that's, that's not particularly tied to smooth spaces, you know, vector spaces that can, it's one that works for manifolds. It's also one that works that we have now used, you know, me and my collaborators and my PhD, that we have used to connect to game theory, where we talk about economic agents that have some strategies. And if we want two agents to operate with the same strategy, we do weight sharing there. So there's all these different fields where you can specify what these are. And the level of abstraction of a two 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.

• 28:55Tim Scarfe?

  You could presumably just go to the third order and to the fourth order. I mean, even with self-attention transformers, they model these two tuples, you know, which is like a second, you know, like a first order relationship. You could have third order, fourth order and so on. Is two morphisms enough or should we go deeper than that?

• 29:15Speaker 07

  Well, depending on who you ask, you will get very opinionated answers. But generally, you know, when I started learning category theory, I was like, well, I'm never going to go to two categories. That seems complicated. Now I say I'm never going to go higher than two categories because that seems too complicated. But people do three categories, infinity categories. And you can really start building up these relationships higher and higher and get this really comprehensive theory that that becomes a very different beast in some ways.

• 29:40Tim Scarfe?

  There is a school of thought that our brain works in this way. So we think using like the symbols and these categories and so on. And then there's the notion of 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.

• 30:02Speaker 07

  That's a big question.

• 30:06Speaker 07

  It's

• 30:08Speaker 07

  What happens with these things is that when we start adding more levels, right, 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 most aptly described as emergent effects, right? Because if you have two things and you want to study their behavior as a composite, well, 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. And 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 track, you start to track. Since this isn't an equality anymore, you have to start tracking this higher self. But now this itself might be a part of another system

• 30:51Speaker 07

  that gives rise to this plethora and levels and levels of emergent effects. So that's one of the problems with higher category theory is that it's just so hard for us, for our complexity of minds, to do this. So it's certainly an open question of what is the best substrate? How to encode these things? And people have done a lot of work in programming language theory of encoding not just data structures and algorithms, but type theories that these algorithms are hosted in in some categorical way.

• 31:18Tim Scarfe?

  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 are computationally intractable. It's very difficult to go between them. But we want to have some kind of a theoretical framework that captures the whole thing, right? You know, captures the emergent organization as well as what's going on underneath.

• 31:41Speaker 07

  So this is one of the goals that you could say is one of the goals of category theory is 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 you set up the 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 what, where this could go, but we're certainly striving to make things as compositional as they could be. And in many of these fields where we have plenty of experimental evidence and lack of good theories, category theory has a very good vantage point and just a lot of practical benefit of let's stop and see what's the good vantage point here.

• 32:25Tim Scarfe?

  Does two morphisms allow us to think about weight tying?

• 32:29Speaker 07

  Absolutely. So if we think about a parametric morphism, as it's a map from A to B with a parameter P, we can often, we often want to change the parameter space. We often want to say do the weight time, which you know, in practice means we start from a smaller weight space and copy the weights in particular. So a two-morphism in the two category of parametric functions is a reparametrization. So it's a, it's a map between two parametric morphisms that, that is somehow coherent. There are some diagrams that have to be satisfied, but essentially they encode that one is obtained by pre-composing some way, some form of weight time, but it doesn't have to be just copying, right? That's the thing we're finding out. It can be arbitrary relationships within the weights. So one of, one of the things that these two cells

• 33:14Speaker 07

  and two morphisms allow us is to see this algebraic structure encoded as relationships between the weights. And then that goes again into what category theory is about. It's about finding relationships between objects and this. So, so absolutely.

• 33:28Tim Scarfe?

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

• 34:05Speaker 00

  When you write code, you, you encounter syntax errors. You don't so much encounter semantics errors. So the syntax is really quite grounded in the things that you're actually typing in when you're, when you're writing something, whether it's an ordinary algorithm, whether it's a network architecture, et cetera. The semantics is much more about like how can programs behave? And you know, one example of this for, we have something like list types. So 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.

• 34:48Speaker 00

  So like numbers with addition, they're a sort of foldable type. If I have a list of numbers, I can just add them to sort of remove the list. And now these, these foldable types, mathematicians have a very different name for them. Monoids, which are a more general kind of group. But in any case, like that's sort of the, 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 two different syntaxes can describe the same thing very easily.

• 35:32Speaker 00

  You know, 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 two 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.

• 36:14Tim Scarfe?

  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 two algebras for the same endofector. The endofector 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 two 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.

• 37:00Speaker 00

  So what is the syntax, for example, of the action of a group? It's really, you kind of say, well, I want to just think I have like one kind of thing, and then each group element takes that thing and makes it, sort of sends it back to itself. So I have sort of a single type, and then each group action does something to that type. So 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.

• 37:45Speaker 00

  So for example, lists, you cannot deal with the syntax of lists using just a single sort. You need a multi-sorted syntax. So the way that you can do this is to say, well, think of, we have sort of zero tuples, one tuples, two tuples, et cetera. And then, 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? So that's a syntax in the same way that group elements were a syntax. And it does have compositionality.

• 38:27Speaker 00

  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? There's, you can't sort of 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. And in the case of groups, a model in sets means a set acted on by the group.

• 39:08Speaker 00

  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. Like, there's just something where the mathematical reasoning just works better if you expand your universe of objects a little bit, even if you only care about the original objects. So this is a lesson that mathematicians have learned many times. And it's sort of why a lot of people will prefer to work on the semantic side,

• 39:52Speaker 00

  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 sort of 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, so 0 through 9 on it. 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 sort of this little mechanism that when it, when the wheel goes from 9 to 0,

• 40:35Speaker 00

  it turns the next wheel by 1. And this is very simple, but it's extremely at odds with the way that GNNs have been conceived of in the past. Because in the past, you, 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 this date, 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.

• 41:18Speaker 00

  So it somehow is a very fundamental aspect of how we assemble more complicated computational operations from simpler ones. I mean, one of the first things that you do if you're describing a CPU is you have to 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

• 42:02Speaker 00

  turns out to be really interesting. The simplest examples of this phenomenon don't occur until you're dealing with three-dimensional manifolds. So you would need to be thinking about things in four-dimensional space. And the simplest example that we know of is the so-called Hopf vibration. This is a situation where you can decompose a three-dimensional sphere, so it's a sphere in four dimensions. You can project it onto a two-dimensional sphere so that all of the pre-images are one-dimensional spheres or circles. And the three-dimensional sphere is very different from the product of the one- and two-dimensional spheres. Just the same way that z mod 100 is very different

• 42:47Speaker 00

  from the product of z mod 10 with z mod 10. And so this is something that I'm personally very excited about right now, coming out of this asynchronous work, is are there ways to exploit this type of geometric subtlety to create the phenomenon of carrying and actually properly model this aspect of algorithmic reasoning and start to build actual CPUs in neural networks?

• 43:15Tim Scarfe?

  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.