kernelfoundry.algorithm.qd_gradient

Quality-Diversity Gradient Module for MAP-Elites Kernel Evolution

This module implements gradient-based enhancements for MAP-Elites, inspired by: - CMA-ME (Covariance Matrix Adaptation MAP-Elites) - Fontaine et al., 2020 - PGA-MAP-Elites (Policy Gradient Assisted) - Nilsson & Cully, 2021 - DQD (Differentiable Quality-Diversity) - Fontaine & Nikolaidis, 2022

Design Philosophy

In standard MAP-Elites, we only track WHERE solutions are (behavioral coordinates) and HOW GOOD they are (fitness). We lose information about: - Which parent→child transitions yield improvements - Which “directions” in behavior space are promising - Historical success rates for different mutation strategies

This module captures “gradient-like” signals from evolutionary transitions to: 1. Guide parent selection toward productive regions 2. Inform mutation direction hints for the LLM 3. Identify high-potential transition pathways 4. Enable adaptive exploration based on historical success

Architecture

• TransitionRecord: Immutable record of a single evolution step

• TransitionStatistics: Aggregated statistics for a behavioral cell

• GradientEstimator: Computes gradient approximations from transition history

• TransitionTracker: Main class integrating all components

Thread Safety

All public methods are thread-safe via internal locking. The tracker can be safely used from multiple worker processes.

Memory Efficiency

• Circular buffer limits memory usage to configurable max_history

• LRU eviction for per-cell statistics

• Compact data structures using __slots__ where applicable

Functions

compute_improvement_heatmap(tracker[, dim1, ...])	Compute a 4×4 heatmap of improvement rates for two dimensions.
compute_transition_matrix(tracker[, dimension])	Compute a transition probability matrix for a single dimension.

Classes

CellStatistics(coords, int, int, int], ...)	Aggregated statistics for a single behavioral cell.
GradientEstimator([fitness_weight, ...])	Estimates gradients in behavior/fitness space from transition history.
GradientType(value)	Types of gradient estimates.
TransitionOutcome(value)	Classification of transition outcomes.
TransitionRecord(parent_id, child_id, ...[, ...])	Immutable record of a single parent→child evolutionary transition.
TransitionTracker([max_history, ...])	Main class for tracking evolutionary transitions and computing gradients.

class kernelfoundry.algorithm.qd_gradient.TransitionTracker(max_history: int = 10000, max_cell_cache: int = 256, gradient_estimator: GradientEstimator | None = None, checkpoint_interval: int = 100)

Main class for tracking evolutionary transitions and computing gradients.

This is the primary interface for the gradient-enhanced MAP-Elites system. It maintains a history of transitions, computes per-cell statistics, and provides gradient-based sampling and mutation guidance.

Usage

1. Create tracker with configuration

2. Call record_transition() after each parent→child evolution

3. Use get_gradient() to get mutation direction hints

4. Use get_sampling_weights() to bias parent selection

5. Periodically call save_checkpoint() for persistence

Integration with MAP-Elites

The tracker integrates with OptimizationAwareDatabase via:

• record_transition(): Called after add() with parent/child info

• get_sampling_weights(): Called during sample() to weight parent selection

• get_mutation_hints(): Called during prompt construction

__init__(max_history: int = 10000, max_cell_cache: int = 256, gradient_estimator: GradientEstimator | None = None, checkpoint_interval: int = 100)

Initialize transition tracker.

Parameters:

• max_history – Maximum number of transitions to keep in memory

• max_cell_cache – Maximum number of cells to track (should be ≥ grid size)

• gradient_estimator – Custom gradient estimator (uses default if None)

• checkpoint_interval – How often to auto-checkpoint (0 = disabled)

set_output_dir(output_dir: str) → None

Set output directory for checkpoints.

record_transition(parent_id: str, child_id: str, parent_coords: Tuple[int, int, int, int], child_coords: Tuple[int, int, int, int], parent_fitness: float, child_fitness: float, is_new_cell: bool = False, is_elite_replacement: bool = False, iteration: int = 0, mutation_hint: str | None = None) → TransitionRecord

Record a single evolutionary transition.

This is the main entry point for tracking. Call this after each parent→child evolution step.

Parameters:

• parent_id – Unique ID of parent program

• child_id – Unique ID of child program

• parent_coords – Parent’s behavioral coordinates

• child_coords – Child’s behavioral coordinates

• parent_fitness – Parent’s fitness at time of evolution

• child_fitness – Child’s fitness after evaluation

• is_new_cell – True if child discovered a new cell

• is_elite_replacement – True if child replaced the elite

• iteration – Current evolution iteration number

• mutation_hint – Optional description of mutation applied

Returns:

The created TransitionRecord

get_gradient(coords: Tuple[int, int, int, int], empty_cells: List[Tuple[int, int, int, int]] | None = None, low_quality_cells: List[Tuple[Tuple[int, int, int, int], float]] | None = None, max_score: float = 1.0, use_cache: bool = True) → Tuple[Tuple[float, float, float, float], Dict[str, Any]]

Get gradient estimate for a cell.

Parameters:

• coords – The behavioral coordinates to compute gradient for

• empty_cells – List of empty cells (for exploration gradient)

• low_quality_cells – List of (coords, score) for low-quality cells

• max_score – Maximum possible score (for normalization)

• use_cache – Whether to use cached gradients

Returns:

Tuple of (gradient_vector, metadata_dict)

get_mutation_hints(coords: Tuple[int, int, int, int], threshold: float = 0.2, max_hints: int = 3) → List[str]

Get human-readable mutation hints based on gradient at a cell.

These hints can be injected into LLM prompts to guide optimization direction.

Parameters:

• coords – Current behavioral coordinates

• threshold – Minimum gradient magnitude to generate hint

• max_hints – Maximum number of hints to return

Returns:

List of mutation hint strings

get_sampling_weights(candidate_coords: List[Tuple[int, int, int, int]], strategy: str = 'improvement_rate') → Dict[Tuple[int, int, int, int], float]

Compute sampling weights for parent selection.

Higher weights indicate cells that are more likely to produce improvements when used as parents.

Parameters:

• candidate_coords – List of candidate cell coordinates

• strategy – Weighting strategy: - “improvement_rate”: Weight by historical improvement rate - “gradient_magnitude”: Weight by gradient magnitude - “combined”: Combination of both

Returns:

Dictionary mapping coordinates to sampling weights

get_best_transition_directions(coords: Tuple[int, int, int, int], top_k: int = 3) → List[Tuple[Tuple[int, int, int, int], float, int]]

Get the most successful transition directions from a cell.

Parameters:

• coords – Source cell coordinates

• top_k – Number of directions to return

Returns:

List of (direction_vector, success_rate, sample_count) tuples

get_statistics() → Dict[str, Any]

Get comprehensive tracker statistics.

get_cell_statistics(coords: Tuple[int, int, int, int]) → Dict[str, Any] | None

Get statistics for a specific cell.

get_recent_transitions(n: int = 100, filter_improvements: bool = False) → List[TransitionRecord]

Get recent transitions from history.

save_checkpoint(path: str) → None

Save tracker state to file.

load_checkpoint(path: str) → None

Load tracker state from file.

class kernelfoundry.algorithm.qd_gradient.TransitionRecord(parent_id: str, child_id: str, parent_coords: Tuple[int, int, int, int], child_coords: Tuple[int, int, int, int], parent_fitness: float, child_fitness: float, fitness_delta: float, outcome: TransitionOutcome, timestamp: float, iteration: int, mutation_hint: str | None = None)

Immutable record of a single parent→child evolutionary transition.

Uses NamedTuple for memory efficiency and immutability guarantees. This is the atomic unit of gradient information storage.

parent_id: str

Unique identifier of the parent program.

child_id: str

Unique identifier of the child program.

parent_coords: Tuple[int, int, int, int]

Behavioral coordinates of parent (4D tuple).

child_coords: Tuple[int, int, int, int]

Behavioral coordinates of child (4D tuple).

parent_fitness: float

Fitness score of parent at time of transition.

child_fitness: float

Fitness score of child after evaluation.

fitness_delta: float

child_fitness - parent_fitness.

outcome: TransitionOutcome

Classification of the transition result.

timestamp: float

Unix timestamp when transition occurred.

iteration: int

Evolution iteration number.

mutation_hint: str | None

Optional string describing the mutation applied.

property transition_vector: Tuple[int, int, int, int]

Compute the direction of movement in behavior space.

property is_improvement: bool

Check if this transition improved fitness.

property behavioral_distance: int

Manhattan distance in behavior space.

to_dict() → Dict[str, Any]

Serialize to dictionary for JSON persistence.

classmethod from_dict(data: Dict[str, Any]) → TransitionRecord

Deserialize from dictionary.

class kernelfoundry.algorithm.qd_gradient.CellStatistics(coords: ~typing.Tuple[int, int, int, int], total_arrivals: int = 0, total_departures: int = 0, improvements_from: int = 0, improvements_to: int = 0, sum_fitness_delta_out: float = 0.0, sum_fitness_delta_in: float = 0.0, discovery_count: int = 0, elite_replacements: int = 0, last_update: float = <factory>, direction_stats: ~typing.Dict[~typing.Tuple[int, int, int, int], ~typing.Tuple[int, int, float]] = <factory>)

Aggregated statistics for a single behavioral cell.

Tracks both incoming and outgoing transition patterns to understand the “flow” of evolution through this cell.

coords: Tuple[int, int, int, int]

The behavioral coordinates of this cell.

total_arrivals: int = 0

Number of children that landed in this cell.

total_departures: int = 0

Number of parents sampled from this cell.

improvements_from: int = 0

Count of improvements originating from this cell.

improvements_to: int = 0

Count of improvements arriving at this cell.

sum_fitness_delta_out: float = 0.0

Sum of fitness deltas for transitions leaving this cell.

sum_fitness_delta_in: float = 0.0

Sum of fitness deltas for transitions entering this cell.

discovery_count: int = 0

How many times this cell was discovered (first filled).

elite_replacements: int = 0

How many times the elite was replaced here.

last_update: float

Timestamp of last update.

direction_stats: Dict[Tuple[int, int, int, int], Tuple[int, int, float]]

property avg_fitness_delta_out: float

Average fitness change for transitions leaving this cell.

property avg_fitness_delta_in: float

Average fitness change for transitions entering this cell.

property improvement_rate_out: float

Fraction of departures that led to improvements.

property improvement_rate_in: float

Fraction of arrivals that were improvements.

update_departure(record: TransitionRecord) → None

Update statistics for a transition leaving this cell.

update_arrival(record: TransitionRecord) → None

Update statistics for a transition entering this cell.

get_best_directions(top_k: int = 3) → List[Tuple[Tuple[int, int, int, int], float]]

Get the most successful transition directions from this cell.

Returns list of (direction_vector, success_rate) tuples.

to_dict() → Dict[str, Any]

Serialize for persistence.

classmethod from_dict(data: Dict[str, Any]) → CellStatistics

Deserialize from dictionary.

__init__(coords: ~typing.Tuple[int, int, int, int], total_arrivals: int = 0, total_departures: int = 0, improvements_from: int = 0, improvements_to: int = 0, sum_fitness_delta_out: float = 0.0, sum_fitness_delta_in: float = 0.0, discovery_count: int = 0, elite_replacements: int = 0, last_update: float = <factory>, direction_stats: ~typing.Dict[~typing.Tuple[int, int, int, int], ~typing.Tuple[int, int, float]] = <factory>) → None

class kernelfoundry.algorithm.qd_gradient.GradientEstimator(fitness_weight: float = 0.4, improvement_rate_weight: float = 0.4, exploration_weight: float = 0.2, min_samples_for_gradient: int = 3, decay_factor: float = 0.95)

Estimates gradients in behavior/fitness space from transition history.

This implements ideas from QD gradient literature: - Natural gradient estimation via finite differences - Importance-weighted gradient averaging - Multi-objective gradient balancing (fitness + novelty)

Mathematical Foundation

For each dimension d ∈ {memory, compute, parallelism, esimd}:

1. FITNESS GRADIENT at cell c: ∂F/∂d ≈ (1/N) Σ (child_fitness - parent_fitness) * sign(child_d - parent_d) where sum is over transitions from c with movement in dimension d

2. IMPROVEMENT RATE GRADIENT: ∂R/∂d ≈ P(improvement | move in +d direction) - P(improvement | move in -d direction) Indicates whether moving in +d or -d is more likely to improve

3. EXPLORATION GRADIENT: Points toward empty/low-quality cells weighted by reachability ∂E/∂d ≈ Σ (max_score - cell_score) * (cell_d - current_d) / distance

The combined gradient is: α*∂F/∂d + β*∂R/∂d + γ*∂E/∂d with α, β, γ as tunable hyperparameters.

DIMENSIONS = ['memory_opt', 'compute_opt', 'parallelism_opt', 'esimd_opt']

__init__(fitness_weight: float = 0.4, improvement_rate_weight: float = 0.4, exploration_weight: float = 0.2, min_samples_for_gradient: int = 3, decay_factor: float = 0.95)

Initialize gradient estimator.

Parameters:

• fitness_weight – Weight for fitness gradient component

• improvement_rate_weight – Weight for improvement rate gradient

• exploration_weight – Weight for exploration gradient

• min_samples_for_gradient – Minimum transitions needed for reliable estimate

• decay_factor – How much to down-weight older transitions

estimate_fitness_gradient(cell_stats: CellStatistics, recent_transitions: List[TransitionRecord]) → Tuple[float, float, float, float]

Estimate fitness gradient at a cell using recent transitions.

Returns a vector indicating which direction improves fitness.

estimate_improvement_rate_gradient(cell_stats: CellStatistics) → Tuple[float, float, float, float]

Estimate gradient based on improvement success rates per direction.

Positive gradient means moving in +d direction improves more often.

estimate_exploration_gradient(current_coords: Tuple[int, int, int, int], empty_cells: List[Tuple[int, int, int, int]], low_quality_cells: List[Tuple[Tuple[int, int, int, int], float]], max_score: float = 1.0) → Tuple[float, float, float, float]

Estimate gradient pointing toward unexplored/underexplored regions.

This encourages exploration of empty cells and improvement of weak cells.

estimate_combined_gradient(cell_stats: CellStatistics, recent_transitions: List[TransitionRecord], empty_cells: List[Tuple[int, int, int, int]], low_quality_cells: List[Tuple[Tuple[int, int, int, int], float]], max_score: float = 1.0) → Tuple[Tuple[float, float, float, float], Dict[str, Tuple[float, float, float, float]]]

Compute combined gradient from all components.

Returns:

Tuple of (combined_gradient, component_gradients_dict)

gradient_to_mutation_hints(gradient: Tuple[float, float, float, float], threshold: float = 0.2) → List[str]

Convert a gradient vector to human-readable mutation hints for the LLM.

Parameters:

• gradient – The gradient vector

• threshold – Minimum absolute value to generate a hint

Returns:

List of mutation hint strings

class kernelfoundry.algorithm.qd_gradient.TransitionOutcome(value)

Classification of transition outcomes.

IMPROVEMENT = 1

NEUTRAL = 2

REGRESSION = 3

CELL_DISCOVERY = 4

ELITE_REPLACEMENT = 5

class kernelfoundry.algorithm.qd_gradient.GradientType(value)

Types of gradient estimates.

FITNESS = 1

IMPROVEMENT_RATE = 2

EXPLORATION = 3

COMBINED = 4

kernelfoundry.algorithm.qd_gradient.compute_transition_matrix(tracker: TransitionTracker, dimension: int = 0) → ndarray

Compute a transition probability matrix for a single dimension.

Returns a 4×4 matrix where entry [i,j] is P(move to level j | at level i). Useful for visualizing transition patterns.

Parameters:

• tracker – The transition tracker

• dimension – Which dimension to analyze (0-3)

Returns:

4×4 numpy array of transition probabilities

kernelfoundry.algorithm.qd_gradient.compute_improvement_heatmap(tracker: TransitionTracker, dim1: int = 0, dim2: int = 1) → ndarray

Compute a 4×4 heatmap of improvement rates for two dimensions.

Entry [i,j] is the improvement rate for transitions from cells with dim1=i and dim2=j (marginalizing over other dimensions).

Parameters:

• tracker – The transition tracker

• dim1 – First dimension index (0-3)

• dim2 – Second dimension index (0-3)

Returns:

4×4 numpy array of improvement rates