Pioneers Insight Method Research Author
Making Deep Learning Perform Real Algorithms with Category Theory
Back to Episodes

Making Deep Learning Perform Real Algorithms with Category Theory

Summary

  • Today’s frontier models imitate computation without reliably executing it. Andrew Dudzik’s test is surgical: change one digit in a patterned addition problem and ChatGPT stops propagating the carry correctly, while Petar Veličković notes that some current frontier models perform “hundreds of billions of multiplications” per token yet cannot reliably multiply small numbers. For investors, capability scale and computational reliability remain distinct thesis variables.
  • Tool use helps, but it does not remove the architectural bottleneck. A model must still predict the calculator’s correct inputs, and longer reasoning chains may require repeated calls, rethinking, and model-tool transitions. Dudzik argues that internalized basic computation “has a chance to be a lot more stable,” with potentially meaningful inference-efficiency gains.
  • Taco Cohen rejects the strongest version of the claim that neural networks cannot learn algorithms. Properly trained models might learn long addition up to memory limits and occasional carrying mistakes, much like humans; neural machinery can execute something symbolic while retaining world knowledge and tolerance for vague concepts. The disagreement is over reliable extrapolation, not whether neural computation can ever resemble a procedure.
  • Geometric deep learning demonstrates the practical value of correct architectural priors. Translation and permutation equivariance restrict the hypothesis space without bias when the symmetry is valid, cutting required data “almost exponentially”; transformers themselves exploit permutation equivariance after token and position embeddings are attached. But group symmetry only describes reversible transformations, while real programs routinely destroy information.
  • Category theory is proposed as the generalization from spatial symmetry to computation itself. Moving from groups to monoids removes invertibility; moving to categories also removes the assumption that every operation composes with every other operation. The ambition is a “periodic table for neural networks” from which architectures can be derived rather than discovered through ad hoc knobs and tweaks.
  • The framework’s concrete targets are recursion, principled weight sharing, and neural implementations of carrying. In a 2-category, weight tying becomes a coherent reparameterization rather than an unexplained coding convention, and the same abstraction can express relationships beyond literal copying. Dudzik’s harder target is a neural adder that transports the information hidden in a state change—potentially a route toward “actual CPUs in neural networks.”
  • Veličković envisions a hybrid rather than a purely neural system. Neural networks would translate noisy reality into an abstract space, with computation handled through learned priors, carefully designed losses, or tool and algorithmic components offering correctness or convergence guarantees. His standard is not 100% accuracy, but systems that know the effort a problem requires and can say, “the problem…is too computationally large for my capabilities.”

Deep dive

1. Scale produces convincing approximations, not dependable algorithms

  • Dudzik’s deliberately categorical opening is, “Language models cannot do addition. Not really.” Give ChatGPT many 8s plus many 1s and it recognizes the trick; change one 8 to a 7, forcing it to stop propagating zeros at the right place, and it either invents an answer or repeats the memorized pattern.

  • Cohen’s pushback—worth keeping—is that an LLM taught properly might learn long addition until memory fails, just as humans forget a digit or mishandle a carry. Whether that procedure is “neural” or “symbolic” matters less to him than the combination: neural machinery can perform an algorithm while absorbing vast world knowledge and handling concepts that resist rigid symbolic definitions.

  • Veličković sees a deeper training misalignment: some current frontier models execute hundreds of billions of multiplications for one token yet cannot reliably multiply relatively small numbers. A potent tool cannot rescue a model that predicts the wrong inputs. Dudzik adds that repeated calls become cumbersome when a reasoning chain contains many small calculations, and therefore sees both stability and efficiency value in internalizing basic computation.

  • The same gap appears in world models: Scarfe says Veo or Genie may look physically realistic under casual inspection without encoding Newton’s three laws “100% accurately.” His practical warning is conditional—these approximations are not yet accurate enough to entrust with robotics.

2. Geometric priors save data but cannot describe destructive computation

  • Cohen argues for abstract priors with “a lot of bang for the buck.” A valid symmetry sharply restricts the hypothesis space without biasing the model, whereas facts such as light switches turning lights on can come from data. A prior that 2D images project a 3D world might be useful; hard-coding every worldly regularity would not be.

  • Veličković grounds equivariance with two examples: shifting a cat image should preserve its label, and permuting a graph’s node order should preserve the graph it represents. Building those guarantees into the architecture can reduce data needs almost exponentially; an ordinary token MLP might require more examples than the trillions already used to learn the permutation behavior transformers possess structurally.

  • The ceiling is invertibility. A permutation can be undone, but Dijkstra or Bellman–Ford compresses many different weighted graphs into identical shortest paths, sometimes with identical lengths; the original graph cannot be recovered. Veličković’s progression therefore relaxes groups first into monoids, removing invertibility, and then into categories, where operations compose only when one function’s output type matches the next function’s input.

  • His hybrid case rests on precedent: FunSearch, AlphaCode, and AlphaGeometry paired language models with genetic algorithms, clustering, or theorem provers that supplied robustness and correctness properties. Neural networks might translate noisy reality into high-dimensional embeddings, while priors, losses, or tools execute the tractable computation—because asking one fixed-budget model to perform both jobs is “likely a bit too much.” His standard is not perfect accuracy: he wants systems to estimate the effort and error risk, or back off when a problem is too computationally large.

3. Category theory aims to turn architecture design into derivation

  • Dudzik demystifies a category as “algebra with colors.” Square matrices behave like magnets that always connect; non-square matrices connect only when dimensions match—an (L \times M) matrix can multiply an (M \times N) matrix because the two (M) “colors” agree. Categories formalize precisely this partial composability across the mixed shapes common in neural networks.

  • Lessard’s structuralist distinction contrasts Descartes, where lines are solution sets to equations, with Euclid, where a line is what stretches between two points. Synthetic mathematics discards inaccessible internal detail as “noise” and retains only relationships that support inference; category theory then supplies one language for group actions, lists, trees, and other structures beyond geometric symmetry’s “one pinprick in the vast.”

  • Cohen values the method because useful definitions fall out systematically. Represent a group as a category, ask for functors into sets, and group representations appear; ask for natural transformations between those functors, and equivariant maps appear. “You don’t have to be clever”; the pieces fit “just like with Lego,” potentially exposing analogous structure-preserving maps in unfamiliar domains.

  • Scarfe’s historical analogy is alchemy before the periodic table: genuine empirical advances without a foundation capable of deriving the next design. Bruno Gavranović describes deep learning as full of ad hoc choices and lacking a unifying framework for its probabilistic, neuroscience, and gradient-based perspectives, then argues that category theory “will become the unifying deep learning framework.” Veličković supplies the immediate problem: classical algorithms compose abstractly, but independently learned latent spaces offer no equally clean stitching rule.

4. Higher categories make weight sharing a mathematical object

  • Paul Lessard explains that an ordinary category has objects and morphisms—generalized functions or arrows—while a 2-category also has 2-morphisms relating those arrows. The extra layer records properties that disappear if neural networks are treated merely as maps, especially relationships among their parameters.

  • In the 2-category of parametric functions, a 2-morphism is a coherent reparameterization. Weight tying can start from a smaller weight space and copy weights into a larger one, but the 2-cells need not encode literal copying: they can express arbitrary coherent relationships among weights. Lessard says the same abstraction works across vector spaces, manifolds, and game-theoretic agents required to use the same strategy.

  • Scarfe asks whether the hierarchy should continue to third, fourth, or higher orders. Lessard’s candid answer is that researchers do study 3-categories and infinity-categories, though he once vowed never to enter 2-categories and now vows never to go higher. The motivation is real: composing systems can produce behavior that differs from studying the components individually and then their joint behavior, leaving a one-way map rather than an equality and generating “levels and levels of emergent effects.”

5. The formal bridge reaches recursion—and exposes the missing carry

  • Dudzik separates syntax, what programs are written from, from semantics, how they behave. Addition plus negation and subtraction can be different syntaxes with the same semantics, making the semantic view better for mathematical analysis and theorem proving. Lists likewise have a recursive syntax but a foldable semantics: a list of numbers disappears under addition, and mathematicians generalize such foldable structures as monoids.

  • Scarfe states the central construction: view a neural layer as a homomorphism between two algebras for the same endofunctor. The endofunctor specifies computation such as a group action, list fold, or automaton transition; each algebra interprets that computation on particular data, and the homomorphism changes representations while preserving the structure. Group equivariance—and thus geometric deep learning—returns as one special case.

  • Group actions use a single-sorted syntax because every transformation sends one type back to itself. Lists require multiple sorts—zero-tuples, one-tuples, two-tuples, and operations packing their elements into further lists—and those operations are highly non-invertible. Their models are foldable types or monoids, giving a semantic way to analyze this recursive computation without forcing it into the group template.

  • Dudzik’s sharpest engineering example is carrying. Two modulo-10 number wheels need a mechanism that advances the second when the first crosses 9 to 0, yet the state change alone cannot reveal whether the cause was +1, +11, or −9. Continuous, gradient-trained GNNs struggle to transport that information; he links the geometry to the Hopf fibration and asks whether it can support carries and ultimately “actual CPUs in neural networks.”