Analysis of Memory-Runtime Trade-offs in Caching Strategies for Genetic Programming Symbolic Regression

AI summary

Overview

Research area: Evolutionary computation, specifically Genetic Programming Symbolic Regression (GPSR), and the caching strategies used to speed up fitness evaluation.

Technical level: Intermediate — readers should be comfortable with genetic programming concepts such as populations, generations, fitness evaluation, and standard cache replacement policies (LRU, LFU, FIFO, RR).

Scope: The paper benchmarks four cache replacement policies across seven cache sizes on three PMLB datasets, quantifies memory-runtime trade-offs, and derives practical cache-sizing guidelines for gplearn users.

What This Paper Is About

GPSR spends much of its runtime repeatedly recomputing the same expressions and sub-expressions, because new candidate expressions are usually modifications of high-fitness expressions from earlier generations. Caching intermediate results can avoid that redundant work, but prior work mostly applied a single caching strategy, so there was little evidence about which policy or cache size actually helps. This paper measures the runtime and RAM consequences of LRU, LFU, FIFO and Random Replacement at multiple cache sizes, and turns those measurements into configuration guidelines.

Key Contributions

1. The authors enhanced GPSR (gplearn) with a caching mechanism that caches sub-expression results during the execute function, reducing fitness computation runtime.
2. They conducted a comprehensive comparison of multiple caching strategies (LRU, LFU, FIFO, RR) and cache sizes, analyzing training runtime, memory consumption, and the trade-off between them.
3. They investigated whether proactively clearing the cache every n generations accelerates training, comparing different clearance intervals.
4. They ran access-count tests under an infinite cache, proposed the "RAM hour" metric to quantify memory-runtime trade-offs, and provided reference guidelines for choosing cache sizes and configuration strategies.

Main Findings

• Fitness evaluation dominates runtime in the baseline: In the original gplearn, the cumulative runtime of the execute function accounts for nearly 50% or even more of overall runtime. Baseline measurements were 657.3 ± 24.8 s overall and 330.2 ± 20.6 s execute for 344_mv, 918.4 ± 230.8 s and 591.7 ± 223.3 s for 215_2dplanes, and 2094.2 ± 9.3 s and 1445.1 ± 9.7 s for 1203_BNG_pwLinear.
• Caching removes the bottleneck: With a sufficiently large cache, the execute runtime accounts for only about 10% of overall runtime; on 344_mv with a cache size of 10k under LRU, the proportion dropped below 5%.
• LRU and FIFO are the effective strategies: For both, increasing cache size reduces overall and execute runtime with diminishing returns. LRU generally gives slightly better runtime improvements than FIFO, except when the cache size is excessively large, where FIFO performs slightly better.
• LFU is unsuitable: LFU consistently underperformed LRU and FIFO at the same cache sizes, and with excessively large caches its runtime increased significantly — in some cases exceeding the original gplearn.
• Random Replacement is weak but competitive at small sizes: RR performed relatively weakly overall, yet at small cache sizes (100 or 500) it performed almost as well as LRU.
• Memory scales with cache size: Both average and peak RAM usage increased almost proportionally with cache size, regardless of cache policy, indicating a linear relationship. For example, on 215_2dplanes the LRU average RAM rose from 171.2 ± 0.8 MB at cache size 100 to 20459.2 ± 560.7 MB at cache size 100k.
• Oversized caches can be pointless: On 344_mv, RAM usage at 50k and 100k was almost identical, because the fitting result was too simple for the expressions to fill a 100k cache.
• Modifying gplearn also removed an overhead: The original gplearn computes out-of-bag fitness regardless of max_samples, which consumes extra RAM; the modified version always sets max_sample to the default of 1 and removed that code, so original gplearn uses even more memory than cached gplearn at cache size 100.
• Proactive cache clearing does not help: On a synthetic dataset with 10,000 samples, population size 10,000, 15 generations, and target y = x0³ + x1² + x0 + sin(x1) + sin(x0²), clearing the cache every 1, 2, 3, 4 or 5 generations had almost no statistically significant effect on overall or execute runtime (clearing every 1 generation: 79.21 s overall, 17.75 s execute; never clearing: 80.54 s and 18.48 s).
• A small share of cached items serves most calls: Under an infinite cache, the cache was invoked 273,553 times. The top 6,070 most frequently accessed items accounted for 90% of total calls while representing only 2.41% of the entire cache size, and the top 5,000 items alone accounted for 203,305 calls, or 87.87% of the total. Runtime improvements nearly diminished beyond a cache size of 5,000.
• RAM hour identifies optimal settings: Using RAM Hour = Max RAM Usage (GB) × Execution Time (hours), the lowest RAM hour for 344_mv and 1203_BNG_pwLinear occurred with LRU at cache size 1,000. For 215_2dplanes, RAM hour generally increased with larger cache sizes, rising slowly before 1,000 and more pronounced afterwards, making 1,000 a balanced choice.
• Dataset complexity changes the recommendation: For 344_mv (random state 1, LRU), where the fit y = div(add(X5, X0), div(X8, X7)) is short, a cache size of 5,000 reduced execute runtime from 302.4 s to 11.1 s and further increases gave no substantial improvement. For the much longer 215_2dplanes fit, raising the cache to 10,000 reduced execute runtime only from 1261.3 s to 415.5 s, while 50,000 continued to reduce it to 214.5 s.

Methodology in Plain English

The authors modified only the execute function of gplearn so that while the program tree is traversed from the root toward the leaves, any sub-expression already stored in a dictionary-style cache is fetched instead of recomputed, with its result written to the cache as the bottom-up numerical evaluation passes back through that node. Cache replacement policies came from the cachetools library, so that LRU, FIFO, LFU and RR could be compared fairly while the rest of gplearn remained generic.

Experiments used three PMLB datasets — 344_mv and 215_2dplanes, both with dimensions (40768, 10), and 1203_BNG_pwLinear with dimensions (177147, 10). Each dataset was split 75:25 into training and test sets with random states 0 through 7. The stopping criteria was set to 0 to force exactly 500 generations, which keeps the computational load consistent across seeds. Hyperparameters followed the SRBench defaults (population size 1000, tournament size 20, crossover probability 0.9, function set add/sub/mul/div, mean absolute error metric). Runtimes and RAM were recorded with cProfile and memory_profiler on a clean Google Cloud Platform c3-highcpu-22 instance, and means and standard deviations were computed from values between the 25th and 75th percentiles to remove anomalous readings. Test performance (R² of 0.965, 0.894 and 0.568, and MAE of 0.658, 1.102 and 2.109 for the three datasets) was recorded as a reference, since caching does not affect prediction performance.

Why This Matters

This is one of the few studies to compare caching policies for GPSR head-on rather than adopting a single strategy, and it reframes cache configuration as a resource-allocation problem via the RAM hour metric. It shows that a lightweight policy such as LRU or FIFO with a modest cache can cut fitness evaluation time by an order of magnitude or more, while a more complex policy (LFU) can actively hurt performance.

Real-world applications of the underlying technique:

• Discovering interpretable mathematical models in physics, finance, biology, materials science, and engineering sectors, where the paper notes symbolic regression has demonstrated utility.
• Large-dataset regression tasks where fitness evaluation accounts for half or more of total runtime and is the primary bottleneck.
• Cloud or server-rental workflows where both peak RAM and wall-clock time translate directly into cost.
• Batch experiments that need statistically significant results across many datasets or random seeds and must decide how many runs to place on one machine.

Industry relevance: The paper's guidelines are aimed at practitioners running GPSR under real compute budgets. If RAM is unconstrained, larger caches (10,000 to 100,000 under LRU or FIFO) still reduce runtime; if resources matter, the paper recommends choosing the cache size that minimizes RAM hour and then running as many GPSR instances in parallel as the server's maximum memory divided by the peak RAM usage at that optimal setting, which is described as leaving server memory at 100% utilization with the shortest total runtime.

Future Directions

• Whether the recommended thresholds (notably cache size 1,000 for the two datasets where RAM hour was minimized) generalize to datasets whose complexity cannot be quantified a priori, since the authors note real-world dataset complexity is often not known in advance.
• How to automate the preliminary analysis the paper recommends — generating memory-runtime plots and applying a method such as the elbow method to pick cache size.
• Whether different caching policies or hybrid policies could outperform LRU and FIFO on the very long expressions seen in the 215_2dplanes fit, where runtime was still decreasing at cache size 50,000.
• How the RAM hour framework applies to symbolic regression tools beyond gplearn, given that the authors deliberately chose gplearn because it adheres to Koza's original GP framework rather than adding heuristics such as PySR's multi-population approach, MetaSR's learned fitness measures, or TaylorGP's Taylor polynomial approximations.

Target Audience

Researchers and practitioners in evolutionary computation and symbolic regression who train GPSR models and care about runtime or memory budgets; engineers deploying gplearn on cloud instances; and method developers who want a measured reference for how cache policy and cache size interact with dataset complexity before designing their own caching or fitness-evaluation optimizations.

Authors’ abstract

Genetic Programming Symbolic Regression (GPSR) generates mathematical expressions to model input-output relationships using an evolutionary process. A significant challenge in GPSR lies in the repeated evaluation of entire expressions or their sub-expression, which inflates computational runtime. To address this inefficiency, caching mechanisms have been employed to reduce redundant computations. However, prior studies predominantly employ a single caching strategy, offering limited insights into their comparative performance or memory-runtime trade-offs. In this paper, we present a comprehensive analysis of caching mechanisms for GPSR on synthetic and real-world datasets. We also include an empirical study of key-value usage frequencies under an infinitely large cache, offering insights into optimal cache sizing. Furthermore, we provide actionable guidelines for configuring caching strategies based on computational and memory constraints. Our findings indicate that complex caching mechanisms necessitate a minimum cache size to achieve computational time reductions. Conversely, lightweight caching strategies, such as Least Recently Used (LRU) and, notably, First-In-First-Out (FIFO), can significantly decrease computation time for fitness evaluations, which are a substantial component of the overall runtime.