TL;DR
AutoNumerics-Zero uses evolutionary algorithms to discover new implementations of fundamental mathematical functions (like $2^x$ and $\log_2 x$) from scratch. These "evolved" functions not only provide orders of magnitude more precision than traditional mathematical methods for the same number of operations but can also achieve a 3x speedup in practical settings by inadvertently "hacking" compiler optimization heuristics.
What Problem Does This Paper Address?
Transcendental functions—like exponentials, logarithms, and trigonometric functions—are the bedrock of scientific computing. Because computers can only perform basic arithmetic (addition, multiplication, etc.), these complex functions must be approximated. For centuries, mathematicians have developed approximation methods like Taylor series, Padé approximants, and minimax optimization.
However, these classical methods were often designed for "arbitrary precision"—the ability to get as close to the true value as desired by adding more terms. Modern computers, conversely, operate on fixed-precision data types like float32. There is a "reality gap" between elegant mathematical theory and the messy reality of hardware rounding rules and compiler heuristics. This paper asks: Can an automated system, starting with zero mathematical knowledge, discover better approximations specifically tuned for modern hardware?
Methods
The authors introduce AutoNumerics-Zero, a symbolic regression framework that treats computer programs as directed acyclic graphs (compute graphs). It uses a two-level evolutionary search process:
- Outer Loop (Discrete Optimization): A distributed variant of the Non-dominated Sorting Genetic Algorithm II, called dNSGA-II, evolves the structure of the program. It starts from empty code and applies random mutations (inserting/deleting nodes, reconnecting edges) to find graphs that balance two objectives: high precision and high efficiency (either few operations or high speed).
- Inner Loop (Continuous Optimization): For every candidate program structure, the system uses CMA-ES (Covariance Matrix Adaptation Evolution Strategy) to find the optimal floating-point coefficients (constants) that minimize the approximation error.
Crucially, the system has "zero knowledge" of calculus, asymptotics, or existing numerical methods. It only knows the four basic arithmetic operations: $\{+, -, \times, \div\}$.
Datasets
While not a traditional "big data" paper, the authors used specific numerical sets for training and evaluation:
- Training/Validation Sets: Sets of $10^3$ to $10^4$ evenly spaced values within specific domains (e.g., $[0, 1]$ for $2^x$, $[1, 2)$ for $\log_2 x$).
- Test Sets: Larger sets ($10^6$ values) or, in the case of
float32experiments, an exhaustive test of all possible $2^{32}$ values to ensure the error never exceeds 1 ULP (Unit in the Last Place). - Ground Truth: Generated using higher-precision types (
float80) or exact rational arithmetic with high-order Taylor polynomials to ensure the "labels" were significantly more accurate than the approximations being tested.
Key Insights and Ideas
- Compiler-Aware Evolution: In the
float32case study using JAX and the XLA compiler, the evolved programs were 3x faster than the best human-designed baselines. The "aha moment" was discovering why: the evolved code's structure triggered the compiler to classify the function as I/O-bound rather than CPU-bound. This bypassed a "parallel task assigner" overhead that slowed down the traditional, more "mathematically logical" implementations. - Beyond Polynomials: Traditional methods usually result in polynomials or ratios of polynomials. Evolution discovered novel, "messy" representations that reuse intermediate results in ways humans rarely do, leading to much higher precision for the same "cost" in operations.
- Handling Rounding: Because the evolution evaluates programs directly on hardware, it naturally accounts for floating-point rounding errors (where $a \div b$ is not always exactly $(1 \div b) \times a$), a nuance often ignored by pure mathematical derivations.
- Transferability: Even though the speedups were discovered on a specific CPU (Intel Skylake), the performance gains largely persisted across a decade of different Intel and AMD architectures.
Key Results
- Precision: For real-valued $2^x$ approximations, AutoNumerics-Zero found programs that were orders of magnitude more precise than Taylor, Padé, and Minimax baselines for any given number of operations (e.g., 10 operations yielded a relative error under $5.4 \times 10^{-15}$).
- Speed: In a practical JAX/XLA environment, the evolved $2^x$ function was over 3 times faster than the fastest baseline while maintaining sub-1 ULP error.
- Generality: The method successfully discovered state-of-the-art approximations for $\log_2 x$, the error function ($erf$), and the Airy function ($Ai$), proving it isn't a "one-hit wonder" for exponentials.
Limitations and Future Work
- Compute Cost: The evolutionary search requires a massive amount of compute (running on large-scale datacenter clusters) to find these optimized functions. It is a "one-time investment" that pays off only for functions used billions of times.
- Search Space Constraints: The current search is limited to relatively small programs (up to ~100 nodes). Discovering more complex algorithms, like range reduction or coordinate rotation (CORDIC), might require a more hierarchical or "typed" search space.
- Black-Box Heuristics: While the system exploits compiler heuristics, those heuristics might change in future compiler versions, potentially "breaking" the specific speedups found, though the authors' transferability tests suggest some robustness.
Summary updated