Code Graphs & Embeddings pada Small Coding Agents (arXiv:2610.33958): Eksperimen 79k Episode SWE-bench, Gradien Hop Depth, dan Batasan Representasi Leksikal Satu-Langkah

// Production Implementation: Structural Code Graph & Localization Orchestrator
// Implements Hop-Aware Multi-Step Expansion, Lexical Fallback, and Tool Uptake Monitoring

export type SearchModality = 'lexical_grep' | 'dense_embedding' | 'ast_graph';

export interface GraphNode {
  id: string;
  name: string;
  kind: 'function' | 'class' | 'method' | 'module';
  filePath: string;
  startLine: number;
  endLine: number;
  outEdges: Array<{ targetId: string; type: 'calls' | 'imports' | 'inherits' }>;
}

export interface LocalizationCandidate {
  nodeId: string;
  filePath: string;
  score: number;
  hopDistance: number;
  resolvedBy: SearchModality;
}

export interface LocalizationEpisodeStats {
  issueId: string;
  modelIdentifier: string;
  totalToolInvocations: number;
  modalityCounts: Record;
  maxChainedExpansions: number;
  reachedHopDepth: number;
  submissionFormatValid: boolean;
}

export class CodeGraphLocalizationEngine {
  private nodeRegistry = new Map();
  private fileInvertedIndex = new Map();

  constructor(
    private readonly maxAllowedHops: number = 3,
    private readonly hopPenaltyFactor: number = 0.58 // Median odds ratio dari arXiv:2610.33958
  ) {}

  public registerASTNode(node: GraphNode): void {
    this.nodeRegistry.set(node.id, node);
    const tokens = this.tokenizeLexical(node.name);
    for (const token of tokens) {
      if (!this.fileInvertedIndex.has(token)) {
        this.fileInvertedIndex.set(token, new Set());
      }
      this.fileInvertedIndex.get(token)!.add(node.id);
    }
  }

  // Multi-step graph expansion dengan tracking kedalaman hop & degradasi probabilitas
  public expandGraphNeighborhood(
    seedNodeId: string,
    currentDepth: number,
    visitedNodes: Set
  ): LocalizationCandidate[] {
    if (currentDepth >= this.maxAllowedHops || visitedNodes.has(seedNodeId)) {
      return [];
    }

    visitedNodes.add(seedNodeId);
    const seed = this.nodeRegistry.get(seedNodeId);
    if (!seed) return [];

    const results: LocalizationCandidate[] = [];
    const stepPenalty = Math.pow(this.hopPenaltyFactor, currentDepth);

    for (const edge of seed.outEdges) {
      const target = this.nodeRegistry.get(edge.targetId);
      if (!target || visitedNodes.has(target.id)) continue;

      results.push({
        nodeId: target.id,
        filePath: target.filePath,
        score: 1.0 * stepPenalty,
        hopDistance: currentDepth + 1,
        resolvedBy: 'ast_graph',
      });

      // Rekursi untuk multi-hop chaining (hanya 12-14% agen open-weight yang berhasil melakukannya)
      if (currentDepth + 1 < this.maxAllowedHops) {
        const nextLevel = this.expandGraphNeighborhood(target.id, currentDepth + 1, visitedNodes);
        results.push(...nextLevel);
      }
    }

    return results;
  }

  // Lexical search fallback (Grep Baseline)
  public executeLexicalGrep(queryToken: string): LocalizationCandidate[] {
    const matchedNodeIds = this.fileInvertedIndex.get(queryToken.toLowerCase());
    if (!matchedNodeIds) return [];

    const candidates: LocalizationCandidate[] = [];
    for (const id of matchedNodeIds) {
      const node = this.nodeRegistry.get(id);
      if (node) {
        candidates.push({
          nodeId: node.id,
          filePath: node.filePath,
          score: 0.95, // Tinggi pada Hop 0
          hopDistance: 0,
          resolvedBy: 'lexical_grep',
        });
      }
    }
    return candidates;
  }

  // Verifikasi apakah kandidat lolos ke submission form yang valid
  public validateSubmissionStructure(patchTargets: string[]): boolean {
    if (!patchTargets || patchTargets.length === 0) return false;
    return patchTargets.every(target => target.includes('/') && target.endsWith('.py'));
  }

  private tokenizeLexical(identifier: string): string[] {
    return identifier
      .replace(/([a-z])([A-Z])/g, '$1 $2')
      .toLowerCase()
      .split(/[^a-z0-9]+/)
      .filter(t => t.length > 2);
  }
}