Differentiable Exact Learning
Organizations: Department of Computer Science, EPFL
Abstract
We introduce a framework for differentiable exact learning that couples an unbounded external environment to a state-tracking neural controller, which we train on policy-trajectory observations (PTOs): expert behavior traces that expose observations and actions while hiding internal states. In addition to the learning framework, we introduce Differentiable Finite-State Transducers (DFSTs) which use multilinear updates, support log-parallel training, and emulate arbitrary finite-state controllers, yielding computational universality through environmental interaction. From tiny training datasets, compact DFSTs achieve extreme length generalization on arithmetic and universal-simulation tasks. We replicate the success of DFSTs on RNNs and GRUs, thereby supporting a broader learning recipe: State-Tracking Controller + Unbounded External Environment + PTOs = Extreme Length Generalization. Beyond length generalization, our metric-extraction protocol recovers interpretable discrete controllers from trained DFSTs, which we prove equivalent to the target arithmetic and universal-simulation algorithms. Furthermore, for our Softmax DFST models, simply taking over the transition probabilities yields discrete controllers which provably exactly perform universal Turing-machine simulation and binary arithmetic. Proving exact learning for the neural controllers requires assumptions, which we empirically support. We make our code, training recipes, model weights, and proof checkers publicly available at https://github.com/fanagor/DEL.
Figures & tables
Appendix figures & tables33 assets
Supplementary material from the paper’s appendix.
Appendix
| Framework | Metric | add2 | add10 | mult2 | mult10 |
|---|---|---|---|---|---|
| Neural GPU with Input–Output Data | # Samples | k | – | k | – |
| # Parameters | 10368 | – | 10368 | – | |
| Training Digits | 20 | – | 20 | – | |
| RLG | – | – | |||
| ULG | 2000 | – | 2000 | – | |
| DFST (ours) | # Samples | 25 | 250 | 100 | 10000 |
| Task | # States | Alphabet | Runtime |
|---|---|---|---|
| Grid Agents | |||
| add2 | |||
| add10 | |||
| mult2 | |||
| mult10 | |||
| Turing Machines (simulated by ) | |||
| Task | Updates | Warm-up | ULG / RLG | |||
|---|---|---|---|---|---|---|
| add2 | 11 | 25 | 3 | 500k | 50k | |
| add10 | 19 | 250 | 3 | 4M | 50k | |
| mult2 | 32 | 100 | 5 | 500k | 25k | |
| mult10 | 108 | 10 000 | 5 | 4M | 0 |
| Task | Hidden dimension | Total updates | Warm-up |
|---|---|---|---|
| add2 | 11 | ||
| mult2 | 32 | ||
| add10 | 19 | ||
| mult10 | 108 | ||
| Universal | 15 |
| Task / controller | Clip | Seed | |||||
|---|---|---|---|---|---|---|---|
| add2 / DFST | 11 | 50k | 0 | 1 | 42 | ||
| add2 / RNN | 32 | 0 | 0 | 0.1 | 123 | ||
| add2 / GRU | 32 | 100k | 800k | 0.1 | 17 | ||
| mult2 / DFST | 32 | 25k | 0 | 1 | 42 | ||
| mult2 / RNN | 64 | 0 | 0 | 0.1 | 1 | ||
| mult2 / GRU | 64 | 100k | 200k | 0.1 | 11 |
| Task | Controller | First ULG cap | First RLG cap | Final ULG / RLG |
|---|---|---|---|---|
| add2 | DFST | 200k | 400k | |
| RNN | 100k | 100k | ||
| GRU | 500k | 900k | ||
| mult2 | DFST | 400k | 400k | |
| RNN | 300k | 300k | ||
| GRU | 400k | 400k |
| Program | Tape transformation | Final tape example |
|---|---|---|
| parity | Erases the input and writes the parity of the number of ones immediately after the original word. | |
| shift-left | Moves the entire word one cell left, preserving bit order. | |
| shift-right | Moves the entire word one cell right, preserving bit order. | |
| scaling-A | Performs state-indexed bit-flipping moves, then a symbol-preserving stopping action; see the rule below. | |
| scaling-B | Performs parity-dependent rewrites, changing direction after encountering blanks; the final rewrite stops. | |
| flip | Replaces each bit with in place. |
| Task | PTO steps | Task | PTO steps |
|---|---|---|---|
| parity | 9295 | flip | 9295 |
| cum-sum | 9298 | bit-delete | 24 838 |
| shift-left | 41 806 | shift-right | 54 086 |
| reverse | 14 911 144 | copy | 15 316 822 |
| scaling-A (500) | 25 784 | scaling-B (500) | 427 803 |
| Task | Inputs | Raw states | Raw edges | Quotient states | |
|---|---|---|---|---|---|
| add2 | 100 | 23 | 44 | 22 | |
| mult2 | 100 | 70 | 133 | 61 | |
| add10 | 250 | 52 | 223 | 52 | |
| mult10 | 2,000 | 195 | 1,282 | 182 | |
| universal | 100 | 49 | 78 | 44 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 0 | First left-operand digit | 0 | ||
| 1 | Scan left operand | 0 | ||
| 2 | First right-operand digit | 0 | ||
| 3 | Scan right operand | 0 | ||
| 4 | Skip last right-operand digit | 1 | ||
| 5 | Copy more, or start products | 2 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 22 | Read the last remaining factor bit | 10 | ||
| 23 | Erase operator for factor 0 | 11 | ||
| 24 | First digit of product by 0 | 13 | ||
| 25 | Continue product by 0 | 13 | ||
| 26 | Erase operator for factor 1 | 12 | ||
| 27 | First digit of product by 1 | 14 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 39 | Start summing the product rows | 18 | ||
| 40 | First digit of initial left scan | 19 | ||
| 41 | Left scan after reading zero | 19 | ||
| 42 | Left scan after reading one | 19 | ||
| 43 | Inspect fresh lower leading cell | 20 | ||
| 44 | First digit after lower leading zero | 21 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 0 | First left-operand digit | 0 | ||
| 1 | Scan left operand | 0 | ||
| 2 | First right-operand digit | 0 | ||
| 3 | Scan factor; last bit 0 | 0 | ||
| 4 | Scan factor; last bit 1 | 0 | ||
| 5 | Revisit last factor bit 0 | 1 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 25 | Select remembered factor bit 0 | 10 | ||
| 26 | Select remembered factor bit 1 | 10 | ||
| 27 | Erase operator for factor 0 | 11 | ||
| 28 | Erase operator for factor 1 | 12 | ||
| 29 | First digit of product by 0 | 13 | ||
| 30 | Continue product by 0 | 13 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 52 | Begin one-digit sum; last bit 0 | 18 | ||
| 53 | Begin one-digit sum; last bit 1 | 18 | ||
| 54 | Begin sum; remember last digit 0 | 18 | ||
| 55 | Begin sum; remember last digit 1 | 18 | ||
| 56 | Revisit sole product digit 0 | 19 | ||
| 57 | Revisit sole product digit 1 | 19 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 72 | Read upper units digit | 22 | ||
| 73 | Write units digit 0 below | 24 | ||
| 74 | Write units digit 1 below | 25 | ||
| 75 | Return above, carry zero | 23 | ||
| 76 | Read upper bit, carry zero | 22 | ||
| 77 | Add value zero below | 24 |
| Phase | Read (next phase, write, move) | |||
|---|---|---|---|---|
| 0 | First left-operand digit | 0 | ||
| 1 | Find the input separator | 0 | ||
| 2 | Descend below units digit | 1 | ||
| 3 | Place the working marker | 1 | ||
| 4 | Ensure a digit above marker | 16 | ||
| 5 | Adjacent existing digit | 2 |
| State | Read | |
|---|---|---|
| Phase | Read next phase | |||
|---|---|---|---|---|
| 0 | First left-operand digit | 0 | ||
| 1 | Scan left operand | 0 | ||
| 2 | First factor digit | 0 | ||
| 3 | Scan right operand | 0 | ||
| 4 | Skip last factor digit | 1 | ||
| 5 | Copy or start products | 2 |
| Phase | Expert state | Allowed reading and continuation |
|---|---|---|
| Initial | Read or ; select the matching row from endpoint . | |
| Dispatch | Read ; jump to selection of . | |
| Selection jump | Read ; step left to row index . | |
| Select | Read ; if , cross column ; otherwise change by . | |
| Cross | Read if , and otherwise; enter first source trit. | |
| First source trit | Read any trit; enter remaining source-code scan. |
| Phase | Expert state | Allowed reading and continuation |
|---|---|---|
| Dispatch | Read ; jump to selection of . | |
| Selection jump | Read ; step left to row index . | |
| Select | Read ; if , cross column ; otherwise change by . | |
| Cross | Read if , and otherwise; enter first source trit. | |
| First source trit | Read any trit; enter remaining source-code scan. | |
| Source scan | Trit: repeat. Delimiter : enter first successor trit. |
| State | ||||
|---|---|---|---|---|
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
| State | ||||
|---|---|---|---|---|
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
| Task | Expert states | Spurious states | Tested dimensions | Cap-reaching runs |
|---|---|---|---|---|
| add2 | 11 | 14 | ||
| mult2 | 32 | 38 |
Length Generalization
Length generalization studies whether sequence models trained on short inputs can reliably solve the same tasks on longer sequences.
See all 52 papers