CAGE: Regime-Aware Algorithm Engineering for Coverage Optimization

1 Introduction

• CAGE separates selection policy from a shared bitset substrate so quality and execution-cost differences can be attributed more cleanly to policy and operating condition.Candidates use bitsets, marginal gains are evaluated against a common covered state, and updates use the same bitwise semantics.Source: §1 · p. 2
• The Pareto signature combines intrinsic workload descriptors with measured quality–runtime responses, and regime transitions mark changed Pareto membership or statistically supported crossovers.Descriptors include candidate and universe size, coverage density, candidate-cost dispersion, budget fraction, repetition horizon, and execution substrate; predicting policies for unseen instances is left for future work.Source: §1 · p. 2
• The evaluation varies workload and budget, repeated-decision horizon, and execution substrate, with Math CP-SAT providing an independent quality reference at selected budgets.The 20% and 40% Math solutions cover the full 1115-element universe and are solver-confirmed optimal; lower budgets retain measurable headroom.Source: §1 · p. 2
• CAGE contributes a controlled bitset boundary, an empirical regime-analysis method, and crossover analysis across budget, repeated decisions, and execution substrates.The study aims to characterize when additional optimization work remains justified as operating conditions change.Source: §1 · p. 2

2.1 Maximum coverage and submodular maximization

• Classical maximum-coverage work establishes approximation guarantees and hardness bounds, while lazy, threshold, and stochastic methods reduce marginal-gain computation or trade quality for fewer evaluations [6, 7, 8, 9, 10, 11, 12].CAGE studies engineering variants under a shared coverage representation and execution primitives rather than proposing a new worst-case approximation ratio.Source: §2.1 · p. 3

2.2 Algorithm selection and empirical performance regimes

• Algorithm-selection research maps problem features to algorithms, whereas CAGE reports controlled-sweep Pareto-set changes and crossovers; predictive per-instance selection remains future work.CAGE separates intrinsic workload descriptors from measured responses.Source: §2.2 · p. 3

2.3 Coverage-guided and cost-aware regression testing

• Coverage-guided regression-testing studies motivate a software domain where CAGE treats JUnit methods as candidates, production source lines as coverage elements, and isolated command runtimes as candidate costs.The paper studies a general budgeted coverage objective rather than positioning itself as a replacement for regression-test-prioritization research.Source: §2.3 · p. 3

2.4 Network and sensor-placement workloads

• Epinions trust-network data and a generated BWSN-inspired time-to-detection workload provide distinct non-software coverage structures.The BWSN workload is not a reproduction of published competition scores.Source: §2.4 · p. 4

2.5 Bitset representations and execution substrates

• CAGE uses dense bitsets as a shared abstraction boundary, not as a new bitmap format; the embedded study measures full-system ModelSim/cycle behavior, not FPGA area, frequency, or power.Marginal gains use set differences and population counts, while coverage updates use bitwise unions.Source: §2.5 · p. 4

3.1 Coverage selection

• Candidates cover subsets of a universe, and the selected set is constrained either by cardinality or by a budget on positive candidate costs.The formulation defines the candidate and universe sets and considers both constraint types.Source: §3.1 · p. 4

3.2 Bitset execution model

• The shared bitset model represents each candidate’s coverage and evaluates its marginal gain against the current covered state before updating that state.These gain and update operations are the shared computational interface used by the evaluated strategies.Source: §3.2 · p. 4

3.3 Repeated decisions

• For repeated decisions, preprocessing may be retained across horizon H while dynamic state changes, making amortized sequence cost more relevant than one-shot latency.The coverage matrix remains fixed across the repeated workload.Source: §3.3 · p. 5

3.4 Intrinsic workload descriptors

• Workload descriptors include candidate and universe sizes, incidence density, cost dispersion when applicable, budget fraction, repetition horizon, and execution substrate.Descriptors must be defined independently of the outcomes of the strategies being evaluated.Source: §3.4 · p. 5

3.5 Response, Pareto signatures, and regime transitions

• A strategy is Pareto-dominated when another is no worse in quality and runtime and strictly better in at least one.The empirical Pareto set consists of strategies that are not dominated.Source: §3.5 · p. 5
• Across ordered settings of a controlled axis, the Pareto signature is the sequence of empirical Pareto sets.Swept axes include budget fraction, horizon, cardinality, and bitset width.Source: §3.5 · p. 6
• A change in Pareto signature marks an empirical regime transition; temporal crossover claims require a timing ratio to cross one, with confidence intervals supporting break-even claims under noisy measurements.Quality headroom and runtime amplification are measured outcomes, not input features; “regime” describes observed response rather than a learned universal classifier.Source: §3.5 · p. 6

4 The CAGE Framework

• CAGE’s central abstraction separates strategy decisions from a shared engine that owns bitset representation, marginal-gain evaluation, coverage updates, and related primitives.The boundary supports audited implementations across Python, native C, and an RV32 realization.Source: §4 · p. 6, Figure 1 · p. 7

4.1 Strategy layer

• Policies choose feasible candidates using exact gains, lazy bounds, thresholds, sampling, costs, refinements, or reusable incidence information while consuming the same coverage semantics.The state transition updates the selected set and covered state after each feasible choice.Source: §4.1 · p. 6

4.2 Bitset execution engine

• The execution engine represents candidates as bitsets and supplies shared marginal-gain and state-update kernels, with additional subset and population-count operations.This makes representation an abstraction boundary rather than a property of one selection policy.Source: §4.2 · p. 6

4.3 Strategy families used in the evaluation

• The evaluation spans cardinality, budget-tier, and reuse strategy families; budget tiers progress from lazy ratio-greedy through one-exchange refinement to bounded two-exchange search.Family labels distinguish established patterns from engineering variants, which are not exact reproductions of published algorithms.Source: §4.3 · pp. 7–8, Table 1 · p. 8

4.4 Regime-analysis pipeline

• The regime pipeline keeps intrinsic descriptors and controlled sweeps separate from measured quality–runtime responses, using Pareto sets and supported crossovers as evidence.Response-side quantities such as remaining quality headroom are not treated as known input features.Source: §4.4 · p. 8, Figure 2 · p. 9

4.5 Cross-layer execution

• The embedded realization maps selected kernels to a memory-mapped accelerator on a PicoRV32 RV32IM system; post-synthesis FPGA metrics are outside the current evidence.The hardware experiment tests transfer of the computational abstraction and locates an overhead crossover.Source: §4.5 · p. 8

5.1 Final evidence set and workload selection

• The audited workload set combines Defects4J, Epinions, and a BWSN-inspired workload; Math also supplies a quality-only CP-SAT reference, with structural descriptors used for context rather than prediction.The Defects4J sweep varies budget fraction, while other experiments examine cardinality, repeated decisions, and execution substrate.Source: §5.1 · p. 9, Table 2 · p. 10, Table 3 · p. 10

5.2 Separation of quality and timing

• Quality is established separately from native C timing, with parity checks against coverage, selected count, and total cost; randomized trials likewise separate quality estimation from paired timing blocks.This prevents parallel quality throughput from contaminating timing claims.Source: §5.2 · p. 10

5.3 Timing protocols

• Epinions and BWSN use 200 reseeded quality trials and 21 paired timing blocks; reuse tests five availability sequences across seven outer timing runs.Math and Chart use 21 blocks with 200 timed repetitions and 20 warmups; Time and Mockito use 10 repetitions and 2 warmups per block.Source: §5.3 · p. 10, Table 4 · p. 11

5.4 Use of generative AI

• The author reports using ChatGPT for manuscript organization and revision, code and documentation review, and reproducibility and plotting scripts; the author verified the scientific content.The tool was not treated as an author or autonomous source of scientific evidence.Source: §5.4 · p. 11

5.5 Metrics and statistical summaries

• Metrics vary by experiment: budget tiers report coverage and median native runtime, randomized trials report coverage ratios and paired speedups, reuse reports horizon speedup, and embedded runs report processor cycles.The analysis distinguishes a first median reuse win from a first 95% confidence-interval-supported win.Source: §5.5 · p. 11

6 Evaluation

• Parity checks hold coverage semantics fixed across the evaluated policies, so subsequent differences trace to policy and execution choices.Budget-tier native outputs are checked against deterministic Python quality rows; reuse checks coverage, selected candidates, and active sequences at each tested horizon.Source: §6 · p. 11

6.1 RQ1: How does the quality–runtime Pareto structure change across workload conditions?

• Every audited Defects4J workload changes Pareto membership during the budget sweep, and all four collapse to fast alone by β = 0.20.Table 5 reports the budget-sweep Pareto signatures; the transition point and competitive methods differ by workload.Source: Table 5 · p. 12, §6.1 · p. 12
• At β = 0.05, CP-SAT finds 1039 Math lines without proving optimality; at β = 0.20 and 0.40, it proves 1115/1115 coverage optimal.At β = 0.10, the scaled formulation is solved optimally at 1086, one line above the best tier method; Table 6 is a quality-only reference.Source: §6.1 · p. 12, Table 6 · p. 12
• At β = 0.05, Chart’s practical method adds 27 lines over fast at roughly 11.3× the reported median runtime.Time’s fast method covers 3609 lines in approximately 3.18 ms, while deep covers 3614 in approximately 2.274 s; the frontier collapses to fast after full coverage at β = 0.10.Source: §6.1 · pp. 12–13
• At k = 500, Epinions sampled-lazy 20 has approximately 0.8813 mean coverage ratio and 1.2015× median speedup; at k = 10, BWSN-inspired TTD reaches approximately 0.9111 and 1.6947×.The BWSN-inspired workload is generated for temporal coverage analysis, not a reproduction of published competition numbers.Source: §6.1 · p. 13

6.2 RQ2: When does persistent preprocessing reuse pay off?

• H = 20 is the first tested reuse horizon whose 95% confidence interval lies fully above one; at H = 100, median total speedup is 1.441964×.The H = 100 confidence interval is [1.411861, 1.448990].Source: §6.2 · p. 14, Figure 6 · p. 16

6.3 RQ3: How does the bitset execution model behave on an embedded substrate?

• At one 32-bit word, hardware assistance is slower at 0.877×; at four words, speedup reaches 1.219× and rises to 2.735× at 32 words.The measurements are full-system ModelSim cycles, not post-synthesis FPGA implementation results.Source: §6.3 · pp. 14–15, Figure 7 · p. 16

6.4 Evaluation summary

• Budget, repetition horizon, and substrate each expose changing Pareto membership or crossover behavior, rather than one stable strategy ranking.The evaluation summary identifies budget-dependent refinement levels, a confidence-supported reuse crossover, and a width-dependent embedded crossover.Source: §6.4 · p. 15

• For each audited Defects4J workload, nondominated tier methods change with budget; at β = 0.20, only the low-overhead baseline remains nondominated.The paper treats intrinsic workload descriptors as context for these contrasts, not as causal explanations.Source: §7 · p. 17
• Time, Mockito, and Chart illustrate contrasting descriptor patterns, but cross-workload evidence supports association rather than causal modeling.Time has 4011 candidates and νw ≈0.025; Mockito has higher cost dispersion (νw ≈0.519), while Chart retains a low-budget quality premium.Source: §7 · p. 17
• At 20% and 40%, CP-SAT confirms coverage of Math’s full 1115-element universe, while lower budgets retain headroom.Solver time is kept separate from native timing, and broader exact-solver certification remains future work.Source: §7 · p. 17
• The embedded experiment tests whether the bitset kernel interface survives a substrate change and where fixed interface overhead is amortized, but is limited to simulation.Source: §7 · p. 17
• Regime-aware is an empirical claim here: an adaptive selector based on descriptors and user objectives remains future work requiring separate training and validation.Source: §7 · p. 17

• The evaluated workloads are not exhaustive, and cross-workload descriptor associations do not establish causation or a universal regime taxonomy.Source: §8 · p. 17
• The strategy set omits known maximum-coverage and submodular methods, and some implementations are inspired by broad families rather than exact publication reproductions.Equivalence is not attributed without code-level mapping.Source: §8 · p. 17
• Native timing is tied to the audited MSVC/Windows and CPU-affinity protocol, so absolute timings may differ elsewhere.Time and Mockito use fewer inner repetitions than Math and Chart because the full protocol was prohibitive; all retain 21 timing blocks.Source: §8 · p. 18
• Defects4J candidate cost measures median isolated test-command wall-clock time, including command, JVM, and build overhead, not just in-process test execution.The relevant-test scope concerns selection for a fixed revision, not whole-project test-suite minimization.Source: §8 · p. 18
• CP-SAT provides a quality reference only for Math’s integer-cost budget workload, and its solver runtime is not compared with native C timing.Without exact references elsewhere, claims concern observed Pareto structure and saturation within evaluated strategies unless full-universe coverage gives an upper bound.Source: §8 · p. 18
• The software comparisons hold dense bitsets fixed and therefore do not establish their dominance over sparse or compressed representations.Source: §8 · p. 18
• The time-to-detection study uses a generated BWSN-inspired ensemble, not a reproduction of published BWSN competition results.Source: §8 · p. 18
• Embedded evidence comes from full-system ModelSim and cycle-level evaluation, not FPGA resource, frequency, power, post-synthesis latency, or application-acceleration measurements.Source: §8 · p. 18

• CAGE combines intrinsic workload descriptors, measured quality–runtime response, Pareto signatures, and supported crossovers while holding coverage semantics and the bitset boundary fixed.Source: §9 · p. 18
• Low-budget refinement can add measurable coverage, while extra search can become overhead after saturation; approximation, preprocessing reuse, and specialized execution each show condition-dependent tradeoffs.The Math CP-SAT reference confirms higher-budget saturation while lower budgets retain residual headroom.Source: §9 · p. 18
• The central conclusion concerns operating regimes, not a single algorithm ranking across workload scale, budget, temporal horizon, and execution environment.Source: §9 · p. 18
• A selector that predicts policies from descriptors and user objectives is a possible next step, but prediction lies outside this work’s claims.Source: §9 · p. 19

A Extended Experimental Details

• The frozen v1.0.0 artifact records run directories, method sets, timing protocol, CPU assignments, cooldowns, and hashes; machine-readable summaries support regenerating condensed tables.The artifact is archived at Zenodo.Source: A Extended Experimental Details · p. 19

A.1 Defects4J budget tiers

• Budget fractions are 0.05, 0.10, 0.20, and 0.40; Math and Chart use 21 timing blocks with 200 inner repetitions and 20 warmups.Time and Mockito use 21 blocks with 10 inner repetitions and 2 warmups; native timing and deterministic Python quality are separate.Source: §A.1 · p. 19

A.2 Separated quality/timing experiments

• Quality trials for Epinions and BWSN TTD use independent reseeding, while timing uses separate paired blocks and excludes measurements gathered during parallel quality throughput.Source: §A.2 · p. 19

A.3 Persistent reuse

• The repeated Math experiment tests horizons 1, 5, 10, 20, and 100, and checks coverage, selected candidates, and active sequence for equality in each comparison.It uses active fraction 0.9, five sequences, seven outer runs, and warmup 2.Source: §A.3 · p. 19

B Embedded Realization Details

• The embedded simulation uses PicoRV32 RV32IM with 64 KiB instruction ROM and data RAM, a memory-mapped CAGE accelerator, cycle counter, and simulation mailbox.The accelerator maintains persistent covered state and supports marginal gain, combined gain-and-update, subset, covered-state load/read, and population count; synthesis-specific metrics are absent.Source: B Embedded Realization Details · p. 19

Statements and Declarations

• The author reports no specific funding or relevant competing interests and credits himself with the study’s conception, methodology, software, experiments, analysis, visualizations, and manuscript.Source: Statements and Declarations · pp. 19–20
• Processed inputs, audited results, manifests, measurement data, code, scripts, and reproduction documentation are archived in the CAGE artifact, with third-party materials remaining under original terms.The code is also available in the CAGE GitHub repository and archived as release v1.0.0; CAGE-owned code and documentation use the MIT License.Source: Statements and Declarations · p. 20