Compiling to Linear Neurons

Joey Velez-Ginorio, Nada Amin, Konrad P. Kording, Steve ZdancewicProc. ACM Program. Lang 2026 · DOI

TL;DR

This paper introduces Cajal, a novel programming language that allows discrete algorithms to be compiled into linear neurons. This breakthrough enables direct programming of neural networks, leading to faster learning, improved data efficiency, and easier debugging, bridging the gap between traditional programming and machine learning.

What Problem Does This Paper Address?

We currently program neural networks indirectly. Instead of explicitly defining their functions, we rely on learning algorithms like gradient descent to figure them out from data. While this approach has been incredibly successful, it has limitations: we lack fine-grained control over the learned functions, understanding their behavior can be difficult, and it's challenging to incorporate discrete algorithmic structures directly into neural networks. This is primarily because discrete algorithms are not inherently differentiable, making them incompatible with gradient-based learning. The authors aim to bridge this gap by developing a method to compile discrete algorithms into a form that neural networks can learn from efficiently.

Methods

The core of this work is Cajal, a minimal, typed, higher-order, and linear programming language. Cajal programs are designed to compile into linear neurons, which are essentially linear maps. The key innovation lies in Cajal's linear typing system, which enforces that variables are used exactly once, preventing duplication or discarding. This restriction is crucial for ensuring that Cajal programs can be faithfully translated into linear maps. The authors provide a formal compiler that maps Cajal types to vector spaces and Cajal values to vectors within those spaces. They also introduce a "soft branching" conditional mechanism, which is differentiable and crucial for enabling gradient-based learning, unlike traditional "hard branching" conditionals.

Datasets

The paper uses the MNIST handwritten digit database for training and evaluating the conditional image transformation task.

Key Insights and Ideas

  • Direct Programming of Neural Networks is Possible: The paper demonstrates that discrete algorithms can be directly programmed into neural networks, moving beyond the indirect, learning-centric approach.
  • Linear Typing as a Bridge: The linear typing discipline in Cajal is the key to compiling discrete structures into differentiable linear maps, which are the building blocks of neural networks.
  • Soft Branching for Differentiability: The introduction of a differentiable "soft branching" conditional is essential for enabling gradient-based learning on directly programmed neural network components.
  • Compiler Correctness Matters for Learning: The authors argue that a compiler's correctness, particularly its ability to preserve program behavior, directly impacts the learning dynamics and efficiency of the resulting neural networks.
  • Empirical Validation is Crucial: Due to the inherent complexity of neural network learning, the authors emphasize the importance of empirical experiments to validate theoretical compiler correctness and demonstrate practical benefits.

Key Results

  • Faster and More Data-Efficient Learning: Experiments show that directly programmed neural networks using Cajal learn significantly faster and require less data compared to indirectly programmed networks for the conditional image transformation task. For instance, the direct model consistently outperformed the indirect model across various configurations.
  • Improved Debugging: The ability to directly program neural networks allows for more intuitive debugging. The authors demonstrate how understanding the program structure enabled them to diagnose and fix a bug in the direct model.
  • Conditional Classification Success: Models derived from Cajal programs successfully performed conditional classification tasks (XOR, AND, OR), with directly programmed models often outperforming or matching indirect models.

Limitations and Future Work

  • Expressive Power: Cajal currently lacks certain types like unit, sums, and products, though these are considered simple extensions. More complex extensions like affine functions and infinite data types (natural numbers, trees) present significant theoretical challenges.
  • Efficiency: The number of neurons required to implement a program can grow quickly with type complexity, leading to bilinear scaling. Future work aims to explore ways to improve this scaling, potentially by relaxing the strict requirement of exact implementation by linear maps.
  • Compiler Correctness Theory for Linking: While the paper establishes compiler correctness for closed programs and basic linking, extending this theory to handle a wider range of environments and more complex interactions with nonlinear neurons remains an open area.
  • Infinite Data: Directly programming neural networks with infinite data types is a significant challenge. The authors suggest this might involve compiling to recurrent neural networks and are developing a variant of Cajal for natural numbers.

Summary updated

BibTeX
@article{velezginorio2026compiling,
  author = {Joey Velez-Ginorio and Nada Amin and Konrad P. Kording and Steve Zdancewic},
  title = {{Compiling to Linear Neurons}},
  journal = {Proc. ACM Program. Lang.},
  year = {2026},
  doi = {10.1145/3776677},
}
Figure