NeurIPS paper: NTK theory trains networks to exactly execute binary arithmetic
kfountou · x · 2026-09-19
A NeurIPS 2025 poster, "Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks," tackles whether neural nets can execute binary-encoded algorithmic instructions exactly rather than approximately.
- Uses the Neural Tangent Kernel (NTK) framework to analyze training dynamics of two-layer fully connected networks in the infinite-width limit
- Shows a sufficiently large ensemble can be trained to execute exactly, with high probability, four fundamental tasks: binary permutation, addition, multiplication, and Subtract-and-Branch-if-Negative (SBN)
- Since SBN is Turing-complete, the framework extends to computable functions
- Achieved with only logarithmically many training samples, via structuring data to isolate bit-level rules and controlling NTK-regime correlations to align predictions with target executions
Directly addresses the classic failure of networks to generalize perfectly on discrete operations.
More from Research
- Benchmark author: auditing is a continuous process, not a good-vs-flawed binary — sarahcat21 · 2026-09-19
- OpenDDE plugins to bring structure prediction and protein design into Codex and Claude Code by early October — AllThingsApx · 2026-09-19
- World models vs RAG: why agents need state tracking, not just retrieval — techNmak · 2026-09-19
- 176-Setting Study Dissects Coding Agent Harnesses: Context Management Matters Most on Tight Budgets — _akhaliq · 2026-09-19
- Stanford/Harvard Paper: Agents Fail From Poor Adaptation, Not Low Intelligence — PolarBearby · 2026-09-19
- Turbo-dLLM Open-Sources CSBP, Speeding Diffusion LLM Training Up to 7.59x at 1M Context — Azaliamirh · 2026-09-19