ActKV 2026: Arsitektur Action-Guided KV Cache Management pada Agentic LLM Inference, Pangkas 74% Memori dengan 98.5% Akurasi, dan Akselerasi Throughput hingga 3.97x

// Production Implementation: ActKV Action-Oriented Cache & Dynamic Budget Controller
// Berdasarkan Arsitektur Sistem Operasi USTC (arXiv:2609.31395 - September 2026)
//
// Karakteristik Inti:
// 1. Action-Oriented LRFU Eviction: Menilai entri KV berdasarkan preferensi query token Action.
// 2. Intermittent Attention Protection: Decay factor lambda dan top-p hit mask mempertahankan entri berkontribusi tinggi.
// 3. Confidence-Driven Adaptive Budget: Memantau rata-rata log-probabilitas token teratas dan mendeteksi slope alpha < 0.
// 4. Page-Aware Conflict-Free In-Place Compaction: Menyatukan slot yang dipertahankan ke tail block dalam satu lintasan.

export interface KVCacheSlot {
  pageId: number;
  offset: number;
  logicalIndex: number;
}

export interface KeepScoreEntry {
  slotIndex: number;
  score: number;
  lastHitRound: number;
}

export class ActKVEvictionManager {
  private lambdaDecay: number;
  private topPThreshold: number;
  private keepScores: Map = new Map();

  constructor(lambdaDecay: number = 0.95, topPThreshold: number = 0.90) {
    this.lambdaDecay = lambdaDecay;
    this.topPThreshold = topPThreshold;
  }

  /**
   * Langkah 1 & 4: Memperbarui Keep Score setelah setiap putaran Observation-Reason-Action (ORA)
   * Berdasarkan attention score yang dihasilkan query regio Aksi (Q_act) terhadap Key (K)
   */
  public updateKeepScores(
    actionAttnScores: Float32Array, // Skor atensi regio Action terhadap semua KV entries
    totalEntries: number
  ): void {
    // 1. Urutkan skor atensi untuk menentukan ambang batas top-p (default 90%)
    const indexedScores: Array<{ idx: number; score: number }> = [];
    let sumScore = 0.0;
    for (let i = 0; i < actionAttnScores.length; i++) {
      indexedScores.push({ idx: i, score: actionAttnScores[i] });
      sumScore += actionAttnScores[i];
    }
    indexedScores.sort((a, b) => b.score - a.score);

    const hitSet = new Set();
    let cumulative = 0.0;
    const targetSum = sumScore * this.topPThreshold;
    for (const item of indexedScores) {
      hitSet.add(item.idx);
      cumulative += item.score;
      if (cumulative >= targetSum) break;
    }

    // 2. Terapkan pembaruan LRFU: KS_t(i) = lambda * KS_{t-1}(i) + AttnScore * [hit at t]
    for (let i = 0; i < totalEntries; i++) {
      const prevScore = this.keepScores.get(i) || 0.0;
      const isHit = hitSet.has(i);
      const incomingAttn = isHit && i < actionAttnScores.length ? actionAttnScores[i] : 0.0;
      
      const newScore = this.lambdaDecay * prevScore + incomingAttn;
      this.keepScores.set(i, newScore);
    }
  }

  /**
   * Langkah 5: Pilih Top-K entri KV yang akan dipertahankan sesuai kuota budget B
   */
  public selectRetainedEntries(budget: number): Set {
    const sorted = Array.from(this.keepScores.entries()).sort((a, b) => b[1] - a[1]);
    const retained = new Set();
    const count = Math.min(budget, sorted.length);
    for (let i = 0; i < count; i++) {
      retained.add(sorted[i][0]);
    }
    return retained;
  }
}

export class ConfidenceBudgetMonitor {
  private tokenConfidences: number[] = [];
  private windowSize: number;
  private stride: number;
  private bottomBPercentile: number;
  private scaleUpFactor: number;
  private maxBudget: number;

  constructor(
    windowSize: number = 32,
    stride: number = 8,
    bottomBPercentile: number = 0.20,
    scaleUpFactor: number = 1.25,
    maxBudget: number = 65536
  ) {
    this.windowSize = windowSize;
    this.stride = stride;
    this.bottomBPercentile = bottomBPercentile;
    this.scaleUpFactor = scaleUpFactor;
    this.maxBudget = maxBudget;
  }

  /**
   * Mengumpulkan token-level confidence dari negatif rata-rata log probabilitas top-k token
   */
  public recordTokenLogProbs(topKLogProbs: number[]): void {
    const avgLogProb = topKLogProbs.reduce((acc, val) => acc + val, 0) / topKLogProbs.length;
    // Negatif rata-rata log probabilitas (semakin tinggi semakin peaked/percaya diri)
    const conf = -avgLogProb;
    this.tokenConfidences.push(conf);
  }

  /**
   * Menghitung slope alpha dari trace-level confidence sequence menggunakan first-order linear regression
   */
  public evaluateBudgetAdjustment(currentBudget: number): number {
    if (this.tokenConfidences.length < this.windowSize) {
      return currentBudget;
    }

    // 1. Sliding window dengan minimum pooling
    const intermediateConf: number[] = [];
    for (let i = 0; i <= this.tokenConfidences.length - this.windowSize; i += this.stride) {
      let minVal = Infinity;
      for (let j = i; j < i + this.windowSize; j++) {
        if (this.tokenConfidences[j] < minVal) minVal = this.tokenConfidences[j];
      }
      intermediateConf.push(minVal);
    }

    if (intermediateConf.length === 0) return currentBudget;

    // 2. Ambil nilai-nilai di bawah persentil ke-b (menangkap fase pemulihan/keraguan model)
    const sorted = [...intermediateConf].sort((a, b) => a - b);
    const cutoffIndex = Math.max(1, Math.floor(sorted.length * this.bottomBPercentile));
    const thresholdVal = sorted[cutoffIndex - 1];
    const traceConf = intermediateConf.filter((v) => v <= thresholdVal);

    if (traceConf.length < 2) return currentBudget;

    // 3. Regresi linier sederhana untuk mencari slope (alpha)
    const n = traceConf.length;
    let sumX = 0, sumY = 0, sumXY = 0, sumXX = 0;
    for (let x = 0; x < n; x++) {
      const y = traceConf[x];
      sumX += x;
      sumY += y;
      sumXY += x * y;
      sumXX += x * x;
    }
    const slopeAlpha = (n * sumXY - sumX * sumY) / (n * sumXX - sumX * sumX);

    // 4. Jika alpha < 0 (tren kepercayaan menurun), lakukan ekspansi budget KV
    if (slopeAlpha < 0) {
      const newBudget = Math.min(Math.round(currentBudget * this.scaleUpFactor), this.maxBudget);
      return newBudget;
    }

    return currentBudget;
  }
}

export class PageAwareInPlaceCompactor {
  private blockSize: number;

  constructor(blockSize: number = 16) {
    this.blockSize = blockSize;
  }

  /**
   * Merencanakan pergerakan slot bebas konflik (conflict-free slot planning)
   * Mengonsolidasikan entri yang dipertahankan ke tail block dalam satu lintas komputasi
   */
  public planCompactionSlots(
    totalLogicalBlocks: number,
    budgetEntries: number,
    keepMask: boolean[]
  ): Array<{ srcLogical: number; dstLogical: number }> {
    const targetBlocks = Math.ceil(budgetEntries / this.blockSize);
    const startTailSlot = (totalLogicalBlocks - targetBlocks) * this.blockSize;
    const endTailSlot = startTailSlot + budgetEntries;

    const copyPlan: Array<{ srcLogical: number; dstLogical: number }> = [];
    const dstVacantSlots: number[] = [];

    // Cari slot yang dievakuasi di dalam zona tail (calon tujuan copy)
    for (let slot = startTailSlot; slot < endTailSlot; slot++) {
      if (slot < keepMask.length && !keepMask[slot]) {
        dstVacantSlots.push(slot);
      }
    }

    // Cari slot yang harus dipertahankan yang berada di luar zona tail (sumber copy)
    let vacantIndex = 0;
    for (let slot = 0; slot < startTailSlot; slot++) {
      if (keepMask[slot] && vacantIndex < dstVacantSlots.length) {
        copyPlan.push({
          srcLogical: slot,
          dstLogical: dstVacantSlots[vacantIndex++],
        });
      }
    }

    return copyPlan;
  }
}