cache-optimizations.ts•19.1 kB
/**
* Cache Optimization Utilities for GEPA
* Provides advanced caching features like batch processing, pattern matching,
* memory management, and performance optimizations
*/
import { EventEmitter } from 'events';
import type { ExecutionTrajectory, FailurePattern } from '../../types/gepa';
import type { LLMAdapter } from '../../services/llm-adapter';
/**
* Simple semaphore implementation for concurrency control
*/
class Semaphore {
private permits: number;
private waitQueue: Array<() => void> = [];
constructor(permits: number) {
this.permits = permits;
}
async acquire(): Promise<void> {
if (this.permits > 0) {
this.permits--;
return;
}
return new Promise<void>((resolve) => {
this.waitQueue.push(resolve);
});
}
release(): void {
if (this.waitQueue.length > 0) {
const resolve = this.waitQueue.shift()!;
resolve();
} else {
this.permits++;
}
}
}
/**
* Pattern Matcher for filtering relevant trajectories and optimizing cache usage
*/
// Define types for cache analysis
interface CacheAnalysis {
patterns: FailurePattern[];
metrics: {
hitRate: number;
missRate: number;
evictionRate: number;
avgAccessTime: number;
};
recommendations: string[];
}
interface CachedPattern {
patterns: FailurePattern[];
timestamp: number;
}
interface CachedAnalysis {
analysis: CacheAnalysis;
timestamp: number;
}
interface CacheComponentStats {
overall?: {
hits: number;
misses: number;
hitRate: number;
};
l1?: {
size: number;
entries: number;
};
l2?: {
size: number;
entries: number;
};
timestamp?: number;
}
export class PatternMatcher {
private readonly config: {
maxAnalysisDepth: number;
patternMinFrequency: number;
};
constructor(config: { maxAnalysisDepth: number; patternMinFrequency: number }) {
this.config = config;
}
/**
* Filter trajectories that are likely to contain useful patterns
*/
filterRelevantTrajectories(trajectories: ExecutionTrajectory[]): ExecutionTrajectory[] {
return trajectories.filter(trajectory => {
// Include failed trajectories (more likely to have patterns)
if (!trajectory.finalResult.success) {
return true;
}
// Include low-scoring trajectories
if (trajectory.finalResult.score < 0.7) {
return true;
}
// Include trajectories with errors in steps
if (trajectory.steps.some(step => step.error)) {
return true;
}
// Include recent trajectories for trend analysis
const dayAgo = Date.now() - 24 * 60 * 60 * 1000;
if (new Date(trajectory.timestamp).getTime() > dayAgo) {
return true;
}
return false;
});
}
/**
* Identify similar trajectories for deduplication
*/
findSimilarTrajectories(trajectories: ExecutionTrajectory[]): Map<string, ExecutionTrajectory[]> {
const groups = new Map<string, ExecutionTrajectory[]>();
for (const trajectory of trajectories) {
const signature = this.getTrajectorySignature(trajectory);
if (!groups.has(signature)) {
groups.set(signature, []);
}
groups.get(signature)!.push(trajectory);
}
return groups;
}
/**
* Create a signature for trajectory similarity comparison
*/
private getTrajectorySignature(trajectory: ExecutionTrajectory): string {
const errorSteps = trajectory.steps
.filter(step => step.error)
.map(step => step.action)
.sort()
.join(',');
const successFlag = trajectory.finalResult.success ? 'S' : 'F';
const scoreRange = Math.floor(trajectory.finalResult.score * 10);
return `${successFlag}:${scoreRange}:${errorSteps}`;
}
/**
* Extract pattern candidates from trajectory data
*/
extractPatternCandidates(trajectories: ExecutionTrajectory[]): Array<{
type: string;
frequency: number;
description: string;
examples: string[];
trajectoryIds: string[];
}> {
const patternMap = new Map<string, {
count: number;
examples: Set<string>;
trajectoryIds: Set<string>;
}>();
for (const trajectory of trajectories) {
// Extract error patterns
for (const step of trajectory.steps) {
if (step.error) {
const pattern = this.normalizeError(step.error);
this.updatePatternMap(patternMap, `error:${pattern}`, step.error, trajectory.id);
}
}
// Extract failure patterns
if (!trajectory.finalResult.success && trajectory.finalResult.error) {
const pattern = this.normalizeError(trajectory.finalResult.error);
this.updatePatternMap(patternMap, `failure:${pattern}`, trajectory.finalResult.error, trajectory.id);
}
// Extract performance patterns
if (trajectory.finalResult?.score < 0.5) {
const stepCount = trajectory.steps?.length || 0;
const timeToFailure = (trajectory.steps && trajectory.steps.length > 0)
? new Date(trajectory.steps[trajectory.steps.length - 1]?.timestamp || Date.now()).getTime() -
new Date(trajectory.steps[0]?.timestamp || Date.now()).getTime()
: 0;
if (stepCount > 10) {
this.updatePatternMap(patternMap, 'performance:too_many_steps',
`${stepCount} steps`, trajectory.id);
}
if (timeToFailure > 30000) { // 30 seconds
this.updatePatternMap(patternMap, 'performance:slow_execution',
`${timeToFailure}ms`, trajectory.id);
}
}
}
// Convert to pattern candidates
const patterns: Array<{
type: string;
frequency: number;
description: string;
examples: string[];
trajectoryIds: string[];
}> = [];
for (const [type, data] of patternMap) {
if (data.count >= this.config.patternMinFrequency) {
patterns.push({
type,
frequency: data.count,
description: this.generatePatternDescription(type, data.count),
examples: Array.from(data.examples).slice(0, 3),
trajectoryIds: Array.from(data.trajectoryIds)
});
}
}
return patterns.sort((a, b) => b.frequency - a.frequency);
}
private updatePatternMap(
patternMap: Map<string, { count: number; examples: Set<string>; trajectoryIds: Set<string> }>,
pattern: string,
example: string,
trajectoryId: string
): void {
if (!patternMap.has(pattern)) {
patternMap.set(pattern, {
count: 0,
examples: new Set(),
trajectoryIds: new Set()
});
}
const data = patternMap.get(pattern)!;
data.count++;
data.examples.add(example);
data.trajectoryIds.add(trajectoryId);
}
private normalizeError(error: string): string {
// Normalize common error patterns
return error
.toLowerCase()
.replace(/\d+/g, 'N') // Replace numbers with N
.replace(/['"]/g, '') // Remove quotes
.replace(/\s+/g, '_') // Replace spaces with underscores
.substring(0, 50); // Limit length
}
private generatePatternDescription(type: string, frequency: number): string {
const [category, pattern] = type.split(':', 2);
switch (category) {
case 'error':
return `${frequency} trajectories failed with error pattern: ${pattern}`;
case 'failure':
return `${frequency} trajectories failed with pattern: ${pattern}`;
case 'performance':
return `${frequency} trajectories showed performance issue: ${pattern}`;
default:
return `${frequency} trajectories showed pattern: ${pattern}`;
}
}
}
/**
* Batch Analysis Processor for optimizing multi-trajectory analysis
*/
export class BatchAnalysisProcessor extends EventEmitter {
private readonly llmAdapter: LLMAdapter;
constructor(llmAdapter: LLMAdapter) {
super();
this.llmAdapter = llmAdapter;
}
/**
* Process trajectories in optimized batches with parallel execution
*/
async processTrajectories(
trajectories: ExecutionTrajectory[],
batchSize: number
): Promise<FailurePattern[]> {
const batches = this.createOptimalBatches(trajectories, batchSize);
const results: FailurePattern[] = [];
// Process batches in parallel with concurrency limit
const concurrency = Math.min(3, Math.ceil(batches.length / 2));
const semaphore = new Semaphore(concurrency);
const batchPromises = batches.map(async (batch, index) => {
await semaphore.acquire();
try {
this.emit('batchStarted', { index, size: batch.length });
const result = await this.processBatch(batch);
this.emit('batchCompleted', { index, result });
return result;
} catch (error) {
this.emit('batchFailed', { index, error });
throw error;
} finally {
semaphore.release();
}
});
const batchResults = await Promise.allSettled(batchPromises);
// Collect successful results
for (const result of batchResults) {
if (result.status === 'fulfilled') {
results.push(result.value);
} else {
this.emit('error', result.reason);
}
}
return results;
}
/**
* Create optimal batches based on trajectory characteristics
*/
private createOptimalBatches(
trajectories: ExecutionTrajectory[],
targetBatchSize: number
): ExecutionTrajectory[][] {
const batches: ExecutionTrajectory[][] = [];
// Sort trajectories by complexity (step count) for balanced batches
const sortedTrajectories = [...trajectories].sort((a, b) => a.steps.length - b.steps.length);
let currentBatch: ExecutionTrajectory[] = [];
let currentComplexity = 0;
const maxComplexityPerBatch = targetBatchSize * 10; // Average 10 steps per trajectory
for (const trajectory of sortedTrajectories) {
const trajectoryComplexity = trajectory.steps.length;
if (currentBatch.length >= targetBatchSize ||
(currentComplexity + trajectoryComplexity > maxComplexityPerBatch && currentBatch.length > 0)) {
batches.push(currentBatch);
currentBatch = [];
currentComplexity = 0;
}
currentBatch.push(trajectory);
currentComplexity += trajectoryComplexity;
}
if (currentBatch.length > 0) {
batches.push(currentBatch);
}
return batches;
}
/**
* Process a single batch of trajectories
*/
private async processBatch(trajectories: ExecutionTrajectory[]): Promise<FailurePattern> {
const analysisPrompt = this.buildOptimizedBatchPrompt(trajectories);
try {
const response = await this.llmAdapter.callLLM(analysisPrompt, {
temperature: 0.1, // Lower temperature for more consistent analysis
maxTokens: 4000
});
if (!response || !response.content) {
throw new Error('No content in LLM response');
}
return JSON.parse(response.content);
} catch (error) {
throw new Error(`Failed to analyze batch: ${error instanceof Error ? error.message : String(error)}`);
}
}
/**
* Build optimized prompt for batch analysis
*/
private buildOptimizedBatchPrompt(trajectories: ExecutionTrajectory[]): string {
// Create condensed trajectory data to fit in context window
const condensedData = trajectories.map(traj => ({
id: traj.id,
success: traj.finalResult.success,
score: traj.finalResult.score,
output: String(traj.finalResult?.output || '').substring(0, 200), // Limit output length
error: (traj.finalResult?.error || '').substring(0, 200),
errorSteps: traj.steps
.filter(step => step.error)
.map(step => ({
action: step.action.substring(0, 100),
error: step.error?.substring(0, 100)
}))
.slice(0, 3), // Limit to first 3 error steps
stepCount: traj.steps.length,
duration: this.calculateTrajectoryDuration(traj)
}));
return `
Analyze these ${trajectories.length} execution trajectories to identify common failure patterns and generate improvement recommendations.
Trajectory Data:
${JSON.stringify(condensedData, null, 2)}
Focus on identifying:
1. Common error patterns across trajectories
2. Performance issues (high step count, long duration)
3. Failure root causes
4. Actionable improvement recommendations
Respond in JSON format with:
{
"commonPatterns": [
{
"type": "error_type|performance_issue|logic_failure",
"frequency": number,
"description": "clear description",
"examples": ["example1", "example2"],
"trajectoryIds": ["id1", "id2"]
}
],
"recommendations": [
{
"priority": "high|medium|low|critical",
"type": "add_instruction|clarify_step|add_example|remove_ambiguity|add_constraint|restructure",
"targetSection": "section to modify",
"proposedChange": "specific change",
"rationale": "why this helps",
"expectedImpact": 0.8,
"affectedTrajectories": ["id1", "id2"]
}
],
"overallConfidence": 0.85
}
`;
}
private calculateTrajectoryDuration(trajectory: ExecutionTrajectory): number {
if (!trajectory.steps || trajectory.steps.length === 0) return 0;
const startTime = new Date(trajectory.steps[0]?.timestamp || Date.now()).getTime();
const endTime = new Date(trajectory.steps[trajectory.steps.length - 1]?.timestamp || Date.now()).getTime();
return endTime - startTime;
}
}
/**
* Analysis Memory Manager for caching patterns and analysis results
*/
export class AnalysisMemoryManager {
private readonly patternCache = new Map<string, CachedPattern>();
private readonly analysisCache = new Map<string, CachedAnalysis>();
private readonly cacheTimeout: number;
constructor(cacheTimeout: number) {
this.cacheTimeout = cacheTimeout;
}
/**
* Cache failure patterns with automatic expiration
*/
cachePatterns(key: string, patterns: FailurePattern[]): void {
this.patternCache.set(key, {
patterns: [...patterns], // Clone to prevent mutation
timestamp: Date.now()
});
// Clean up expired entries periodically
this.cleanupExpiredEntries();
}
/**
* Get cached patterns if not expired
*/
getCachedPatterns(key: string): FailurePattern[] | null {
const cached = this.patternCache.get(key);
if (!cached) return null;
if (Date.now() - cached.timestamp > this.cacheTimeout) {
this.patternCache.delete(key);
return null;
}
return [...cached.patterns]; // Clone to prevent mutation
}
/**
* Cache analysis results
*/
cacheAnalysis(key: string, analysis: CacheAnalysis): void {
this.analysisCache.set(key, {
analysis: { ...analysis }, // Clone to prevent mutation
timestamp: Date.now()
});
this.cleanupExpiredEntries();
}
/**
* Get cached analysis result
*/
getCachedAnalysis(key: string): CacheAnalysis | null {
const cached = this.analysisCache.get(key);
if (!cached) return null;
if (Date.now() - cached.timestamp > this.cacheTimeout) {
this.analysisCache.delete(key);
return null;
}
return { ...cached.analysis }; // Clone to prevent mutation
}
/**
* Get memory usage statistics
*/
getMemoryStats(): {
patternCacheSize: number;
analysisCacheSize: number;
totalEntries: number;
oldestEntry: number;
newestEntry: number;
} {
const allEntries = [
...Array.from(this.patternCache.values()),
...Array.from(this.analysisCache.values())
];
const timestamps = allEntries.map(entry => entry.timestamp);
return {
patternCacheSize: this.patternCache.size,
analysisCacheSize: this.analysisCache.size,
totalEntries: allEntries.length,
oldestEntry: timestamps.length > 0 ? Math.min(...timestamps) : 0,
newestEntry: timestamps.length > 0 ? Math.max(...timestamps) : 0
};
}
/**
* Clear all cached data
*/
clear(): void {
this.patternCache.clear();
this.analysisCache.clear();
}
/**
* Clean up expired cache entries
*/
private cleanupExpiredEntries(): void {
const now = Date.now();
// Clean pattern cache
for (const [key, entry] of this.patternCache) {
if (now - entry.timestamp > this.cacheTimeout) {
this.patternCache.delete(key);
}
}
// Clean analysis cache
for (const [key, entry] of this.analysisCache) {
if (now - entry.timestamp > this.cacheTimeout) {
this.analysisCache.delete(key);
}
}
// Limit cache size to prevent memory leaks
const maxEntries = 1000;
if (this.patternCache.size > maxEntries) {
const entriesToDelete = this.patternCache.size - maxEntries;
const sortedKeys = Array.from(this.patternCache.keys())
.sort((a, b) => (this.patternCache.get(a)?.timestamp || 0) - (this.patternCache.get(b)?.timestamp || 0));
for (let i = 0; i < entriesToDelete; i++) {
this.patternCache.delete(sortedKeys[i] || '');
}
}
if (this.analysisCache.size > maxEntries) {
const entriesToDelete = this.analysisCache.size - maxEntries;
const sortedKeys = Array.from(this.analysisCache.keys())
.sort((a, b) => (this.analysisCache.get(a)?.timestamp || 0) - (this.analysisCache.get(b)?.timestamp || 0));
for (let i = 0; i < entriesToDelete; i++) {
this.analysisCache.delete(sortedKeys[i] || '');
}
}
}
}
/**
* Cache Statistics Aggregator
*/
export class CacheStatsAggregator {
private readonly stats: Map<string, CacheComponentStats> = new Map();
updateStats(componentName: string, stats: CacheComponentStats): void {
this.stats.set(componentName, {
...stats,
timestamp: Date.now()
});
}
getAggregatedStats(): {
components: Record<string, CacheComponentStats>;
totals: {
totalHits: number;
totalMisses: number;
overallHitRate: number;
totalSize: number;
totalEntries: number;
};
} {
const components: Record<string, CacheComponentStats> = {};
let totalHits = 0;
let totalMisses = 0;
let totalSize = 0;
let totalEntries = 0;
for (const [name, stat] of this.stats) {
components[name] = stat;
if (stat.overall) {
totalHits += stat.overall.hits || 0;
totalMisses += stat.overall.misses || 0;
}
if (stat.l1) {
totalSize += stat.l1.size || 0;
totalEntries += stat.l1.entries || 0;
}
if (stat.l2) {
totalSize += stat.l2.size || 0;
totalEntries += stat.l2.entries || 0;
}
}
const overallHitRate = totalHits + totalMisses > 0
? totalHits / (totalHits + totalMisses)
: 0;
return {
components,
totals: {
totalHits,
totalMisses,
overallHitRate,
totalSize,
totalEntries
}
};
}
clear(): void {
this.stats.clear();
}
}