
Read the paper
Differentiable Exact Learning
on GitHub
Imagine you're teaching someone to do long multiplication. You don't show them every possible multiplication problem — you show them a handful, explain the carry rules, and trust the mechanism to generalize. The catch with neural networks is that they learn pattern-matching, not mechanism. They nail the training distribution, then collapse on longer inputs. This paper says: what if we forced the neural network to actually learn the carry rules — provably, extractably, exactly? The core claim is a recipe: couple a state-tracking neural controller to an unbounded external environment (like a tape), train it on "policy-trajectory observations" (expert behavior traces that show inputs and outputs but hide internal states), and you get extreme length generalization — not approximate, but exact. The authors introduce Differentiable Finite-State Transducers (DFSTs), compact models that use multilinear state updates and support log-parallel training. From training sets as small as a few dozen examples, these DFSTs learn binary addition, multiplication, and even universal Turing machine simulation, then generalize perfectly to inputs thousands of times longer than anything seen during training. The architectural bet is specific and consequential. DFSTs sit in the finite-state transducer family — not transformers, not SSMs, not attention-based at all. They use multilinear updates over a probability simplex, making them differentiable analogs of classical automata. The external tape provides unbounded memory, which is what lifts these beyond finite-state limitations to computational universality. The log-parallel training trick lets them train efficiently despite sequential structure. Crucially, the authors also replicate the length-generalization result on standard RNNs and GRUs using the same recipe, arguing the magic isn't in the DFST architecture specifically but in the combination of state-tracking controller + unbounded environment + policy-trajectory observations. The integrity story here is unusually strong for a machine learning paper. The authors don't just show empirical generalization curves — they provide mathematical proofs that argmax-extracted discrete controllers from trained Softmax DFSTs exactly implement the target algorithms. They prove equivalence to target arithmetic and universal simulation algorithms. The proofs do require assumptions (which they acknowledge and empirically validate), and they release code, training recipes, model weights, and proof checkers on GitHub. The paper is accepted at NeurIPS 2026, which provides one layer of peer review. What makes this genuinely interesting is what it doesn't do. It doesn't scale to large language model territory. It doesn't handle natural language. It operates on clean algorithmic tasks where "correct" has a crisp definition. But within that scope, it cracks a problem the field has struggled with for years: getting neural networks to learn the actual algorithm, not a statistical shadow of one, and proving they did so. The metric-extraction protocol — recovering interpretable discrete controllers from continuous weights — is the load-bearing novelty. You train a differentiable model, then extract a provably correct discrete machine. The ladder position is clear. Prior work on length generalization (scratchpads, chain-of-thought, positional encodings for transformers) achieves approximate generalization that degrades with length. Classical automata theory gives you exact algorithms but no learning. This paper bridges the gap: differentiable learning that terminates in provably exact discrete algorithms. The gap to watch is whether the recipe scales beyond clean algorithmic tasks to messier domains where "exact" is harder to define. The successor experiment the authors conspicuously did not run: scaling to significantly larger state spaces or tasks where the target algorithm isn't known in advance. The honest read is probably (a) and (c) — they ran out of scope for this paper and are saving harder tasks for follow-up. The framework's promise is broad but the demonstrations are carefully chosen to be provable. Whether this recipe works when you can't write down the target FST is the open question that will determine whether this is a beautiful theoretical result or the seed of a paradigm shift.
The analogy
Teaching someone long multiplication by showing them five worked examples, then proving they internalized the carry rules — not by checking a million test cases, but by extracting the rules from their head and mathematically verifying them against the real algorithm.
Carry rules
Show a student 5 multiplication examples; they internalize the carry mechanism and generalize to any length
DFST extraction
Train a differentiable model on tiny datasets; extract a discrete controller and prove it implements the exact target algorithm
Honest assessment
This is a theoretically beautiful result that solves a real problem — exact algorithm learning with proofs — within a carefully scoped domain. The tasks are clean, the proofs are real, and the code is public. The open question is whether the recipe generalizes beyond tasks where you already know the target algorithm. If it does, this is the seed of automated algorithm discovery. If it doesn't, it's an elegant theoretical contribution to the neural-automata literature. Either way, it's the strongest paper in the 'can neural networks actually learn algorithms?' debate in years.
What Is CLAIMS?
83
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
5/5
Ladder
4/5
Architecture
5/5
Integrity
4/5
Milestone
3/5
Successor
4/5
What is this paper actually committing to?
Genuine first: provably exact algorithm learning from tiny data via differentiable training, with mathematical verification of extracted discrete controllers. Not approximate length generalization — exact, with proofs.
The field fight
Can neural networks learn exact algorithms that generalize to arbitrary input lengths, or are they fundamentally approximate pattern matchers?
Side A
Scale and architecture improvements (transformers, CoT, scratchpads) will close the generalization gap; exact proofs are unnecessary for practical use
Held by: Transformer scaling camp, scratchpad methods, positional-encoding approaches
Side B
Exact algorithm learning requires structured external memory and automata-theoretic foundations; approximation is a dead end for algorithmic tasks
Held by: Neural automata camp, neural Turing machines, this paper
Milestone tracker
Unlocks: Automated algorithm discovery: train a differentiable model, extract a novel provably-correct algorithm no human wrote
Current
Exact
on known algorithms
this paper
Next
Exact
on unknown algorithms
discovery mode
~2-4 years; requires proof machinery that doesn't need known target
Verified Facts (8)
Authors: Hristo Papazov, Francesco D'Angelo, Nicolas Flammarion
Accepted at NeurIPS 2026
DFSTs use multilinear updates and support log-parallel training
Policy-trajectory observations (PTOs) expose observations and actions while hiding internal states
Simply taking argmax over transition probabilities yields discrete controllers which provably exactly perform universal Turing-machine simulation and binary arithmetic
Success replicated on RNNs and GRUs
Code, training recipes, model weights, and proof checkers available at https://github.com/fanagor/DEL
Categories: cs.LG, cs.AI, cs.FL, stat.ML
Practical Implications (4)
Provides a concrete recipe (controller + external memory + PTOs) that practitioners can try on any sequential algorithmic task where exact correctness matters
The metric-extraction protocol offers a path to interpretable, verifiable AI for safety-critical algorithmic applications
Demonstrates that RNNs and GRUs — not just custom architectures — can achieve extreme length generalization with the right training setup
Open-source code and proof checkers lower the barrier to replication and extension by other groups
More latest news
Read all