PKTP (arXiv:2610.31667): Direct Pass@k Optimization for Thought Pruning — Mengatasi Dilema Eksploitasi vs Eksplorasi pada Test-Time Reasoning Melalui Model Gaussian Laten dan Submodular Greedy Selection

1. Paradigma Test-Time Compute Scaling & Batasan Kritis Rollout Pruning

Evolusi penalaran model bahasa besar telah bergeser drastis dari pretraining scale menuju inference-time scaling. Dengan menghasilkan sekumpulan $N$ kandidat lintasan nalar (reasoning rollouts) $y^{(i)} sim pi(cdot|q)$ untuk sebuah pertanyaan rumit $q$, probabilitas menemukan setidaknya satu solusi yang benar (diukur melalui metrik $ ext{pass}@k$) meningkat signifikan. Kendati demikian, menjalankan seluruh $N$ kandidat hingga batas anggaran token penuh $B = 32{,}768$ token sangat mahal dari segi GPU FLOPs, memori High-Bandwidth Memory (HBM), dan latensi end-to-end.

Untuk menghemat komputasi, paradigma Test-Time Pruning membangkitkan $N$ kandidat hanya sampai batas cutoff awal $T$ token (misalnya $T = 4{,}000$ token). Pada titik pemangkasan ini, representasi laten prefix diekstraksi ke dalam vektor embedding $h_i = h(y_{1:T}^{(i)}) in mathbb{R}^d$ menggunakan exponential moving average (EMA) dari hidden states transformer. Sistem inferensi kemudian memilih subset $S subseteq {1, dots, N}$ berukuran $|S| = k$ kandidat yang paling menjanjikan untuk diteruskan ke token penuh $B$, sementara sisa kandidat $N - k$ dieliminasi seketika.

2. Kegagalan Dua Kutub Ekstrem: Ilusi Linear Probe vs Kebocoran RepExp

Hingga saat ini, komunitas rekayasa AI mendekati seleksi kandidat melalui dua pendekatan yang saling bertolak belakang, di mana keduanya gagal mengoptimalkan tujuan utama sistem:

A. Pure Exploitation (Linear Probe): Terjebak Correlated Failure Clusters

Metode Linear Probe melatih pengklasifikasi linear $w in mathbb{R}^d$ di atas vektor representasi prefix $h_i$ untuk memprediksi probabilitas keberhasilan individu: $hat{p}_i = sigma(w^ op h_i)$. Sistem kemudian memilih $k$ rollout dengan skor tertinggi:

Cacat Fatal: Probe mengevaluasi tiap lintasan secara terisolasi tanpa memedulikan dependensi antar-rollout. Akibatnya, rollout yang mendapat skor tinggi cenderung memiliki representasi yang identik dan mengelompok (clustering) pada ruang laten yang sama. Jika probe melakukan kesalahan klasifikasi pada premis tersebut (misalnya salah menginterpretasikan asumsi aljabar yang tampak rapi padahal salah), seluruh $k$ rollout yang dipilih ternyata gagal bersamaan. Pada model skala besar seperti Qwen3-8B di AMO-Bench, 16 rollout teratas pilihan Linear Probe seluruhnya berakhir salah (0% akurasi), sementara seleksi acak mampu menangkap 7 solusi benar!

B. Pure Exploration (RepExp): Menghamburkan Anggaran pada Outlier Cacat

Sebaliknya, pendekatan Representation Exploration (RepExp) memprioritaskan keragaman representasi. Mulai dari satu kandidat acak, RepExp secara rakus menambahkan rollout $i^star$ yang representasinya paling sedikit dijelaskan oleh kandidat yang sudah terpilih:

Cacat Fatal: RepExp sama sekali buta terhadap kualitas solusi. Vektor embedding yang berada paling jauh dari kumpulan utama (outliers) sering kali merepresentasikan penalaran yang ngawur, repetitif, atau melanggar sintaks dasar matematika. Pada pengujian Qwen3-8B di Omni-MATH, RepExp secara konsisten memilih lintasan anomali yang 100% keliru, kalah performa dibandingkan seleksi acak pada nilai $k$ moderat.

3. Formulasi Matematika PKTP: Model Gaussian Laten & Ruang Kovariansi

Untuk keluar dari jebakan heuristik, Salmani et al. (2026) merumuskan masalah pruning secara murni berdasarkan metrik akhir yang ingin dicapai: memaksimalkan probabilitas bahwa setidaknya satu dari $k$ rollout yang disimpan mencapai jawaban benar saat dieksekusi hingga tuntas:

Tantangan matematis mendasarnya adalah: meskipun rollout disampel secara independen dari model $pi(cdot|q)$, luaran akhirnya tidak independen jika dikondisikan pada observasi parsial prefix $y_{1:T}$. Dua rollout yang memiliki prefix serupa memiliki probabilitas tinggi untuk sukses bersama atau gagal bersama.

PKTP memodelkan distribusi gabungan luaran rollout ini menggunakan model Gaussian laten terintegrasi. Misalkan $mathbf{H} = [h_1, dots, h_N] in mathbb{R}^{d imes N}$ merepresentasikan matriks embedding prefix, dan $Q_ heta(h_i) = heta^ op h_i + heta_0$ adalah pemetaan kualitas skalar. Skor laten $Z_i$ untuk rollout ke-$i$ didefinisikan sebagai:

Struktur ini memiliki intuisi fisik yang sangat elegan:

• Kualitas Individual ($q_i = Q_ heta(h_i)$): Mengukur kecakapan intrinsik dari lintasan nalar tersebut.
• Korelasi Antar-Rollout ($mathbf{H}^ op f$): Variabel acak Gaussian bersama $f$ menangkap fitur tak teramati yang mempengaruhi seluruh kandidat. Kovarians bersyarat antara dua kandidat adalah $ ext{Cov}(Z_i, Z_j | mathbf{H}) = h_i^ op h_j$. Artinya, dua rollout yang memiliki vektor nalar sejajar ($h_i approx h_j$) memiliki korelasi luaran positif yang kuat.
• Ambang Batas Biner: Kebenaran akhir dimodelkan dengan thresholding $C_i = 2 cdot mathbf{1}{Z_i ge 0} - 1 in {-1, +1}$.

4. Derivasi Second-Order Surrogate & Pembuktian Garansi Submodular

Probabilitas kegagalan simultan dari seluruh subset $S$ (yaitu semua kandidat dalam $S$ bernilai $C_i = -1$) dinyatakan sebagai:

Karena ekspektasi terhadap $f$ di atas tidak memiliki solusi bentuk tertutup (closed-form), mengevaluasi integral numerik berdimensi tinggi pada setiap langkah seleksi inferensi akan sangat lambat. Peneliti PKTP melakukan ekspansi Taylor orde kedua terhadap $log Phi(-q_i - h_i^ op f)$ di sekitar $h_i^ op f approx 0$, mengubah integral tersebut menjadi integral Gaussian analitik murni:

Dekonstruksi rumus di atas memperlihatkan keseimbangan matematis yang sempurna:

1. Suku Kualitas Modular ($sum_{i in S} log Phi(-q_i)$): Bernilai negatif lebih besar ketika $q_i$ tinggi, mendorong sistem memilih rollout berkualitas nalar tinggi.
2. Suku Diversitas Log-Determinan ($-rac{1}{2} log det(mathbf{I}_d + oldsymbol{Sigma}_S)$): Menghadiahi pemilihan vektor $h_i$ yang merentang (span) dimensi ortogonal baru, mencegah akumulasi arah yang sama.
3. Suku Penalti Redundansi Kolinear ($rac{1}{2} b_S^ op (mathbf{I}_d + oldsymbol{Sigma}_S)^{-1} b_S$): Bernilai non-negatif dan menghukum kandidat yang mengarah pada kuadran yang sama persis ($sum lambda_i h_i$), mendeteksi redundansi yang gagal ditangkap oleh log-determinan saja.

5. Implementasi Algoritma Seleksi Greedy Efisien: Rank-One Update $O(k(Nd + d^2))$

Secara naif, mengevaluasi perubahan determinan dan invers matriks $(mathbf{I}_d + oldsymbol{Sigma}_{S cup {j}})^{-1}$ untuk setiap kandidat $j$ pada setiap langkah greedy membutuhkan faktorisasi matriks $O(d^3)$. Dengan $N = 128$, dimensi embedding $d = 2048$, dan budget $k = 16$, pendekatan naif akan memakan waktu ribuan milidetik per query—membatalkan penghematan test-time compute.

Karena penambahan kandidat tunggal $j$ ke dalam set $S$ hanya menambah matriks rank-satu $kappa_j h_j h_j^ op$, PKTP memanfaatkan Formula Sherman-Morrison dan Matrix Determinant Lemma:

Dengan memelihara vektor perantara $v_j = mathbf{M}_S^{-1} h_j$ secara in-place, kompleksitas seleksi terpangkas drastis menjadi hanya $mathcal{O}(k(Nd + d^2))$ dengan kebutuhan memori statis $mathcal{O}(Nd + d^2)$. Di atas GPU/CPU modern, seleksi 16 kandidat dari 128 rollout selesai dalam waktu kurang dari 4.5 milidetik.

6. Implementasi Produksi TypeScript / Node.js Engine PKTP Selector

Berikut adalah arsitektur kode produksi lengkap untuk modul seleksi PKTP di inference engine, yang mengintegrasikan pemodelan Gaussian laten dan update matriks rank-one secara deterministik:

// Production Implementation: PKTP (Pass@k Thought Pruning) Engine
// Berdasarkan Spesifikasi Formal arXiv:2610.31667 (USC, Oktober 2026)
//
// Karakteristik Inti:
// 1. Latent Gaussian Joint Model with Residual Covariance: Cov(Z_i, Z_j | H) = h_i^T h_j
// 2. Closed-Form Second-Order Surrogate log eL(S) Optimization
// 3. Fast Greedy Submodular Selection with Rank-One Woodbury / Sherman-Morrison Updates
// 4. Complexity: O(k(Nd + d^2)) Time vs Naive O(kNd^3) Factorization

export interface RolloutPrefix {
  id: number;
  embedding: Float64Array; // EMA of hidden states at cutoff T (dimension d)
  tokensGenerated: number;
  qualityScore?: number;   // Linear probe prediction q_i = theta^T h_i + theta_0
}

export interface PKTPConfig {
  d: number;             // Hidden state embedding dimension (e.g. 2048, 4096)
  k: number;             // Target kept rollouts budget (e.g. 4, 8, 16)
  rho: number;           // Latent correlation strength scale
  regularizerTau: number;// Numerical stability epsilon
}

export interface PruningSelectionResult {
  selectedIndices: number[];
  estimatedPassAtK: number;
  executionTimeMs: number;
  surrogateScoresByStep: number[];
}

/**
 * Normal Distribution PDF and CDF helpers
 */
function gaussianPdf(x: number): number {
  return (1.0 / Math.sqrt(2.0 * Math.PI)) * Math.exp(-0.5 * x * x);
}

function gaussianCdf(x: number): number {
  // Abramowitz and Stegun approximation for standard normal CDF Phi(x)
  const b1 = 0.319381530;
  const b2 = -0.356563782;
  const b3 = 1.781477937;
  const b4 = -1.821255978;
  const b5 = 1.330274429;
  const p = 0.2316419;
  const c = 0.39894228;

  if (x >= 0.0) {
    const t = 1.0 / (1.0 + p * x);
    return 1.0 - c * Math.exp(-x * x / 2.0) * t *
      (t * (t * (t * (t * b5 + b4) + b3) + b2) + b1);
  } else {
    const t = 1.0 / (1.0 - p * x);
    return c * Math.exp(-x * x / 2.0) * t *
      (t * (t * (t * (t * b5 + b4) + b3) + b2) + b1);
  }
}

/**
 * PKTP Greedy Submodular Selector
 */
export class PKTPSelector {
  private config: PKTPConfig;

  constructor(config: PKTPConfig) {
    this.config = config;
  }

  /**
   * Menjalankan seleksi k kandidat rollout dari N kandidat prefix
   * Memanfaatkan rank-one update invers matriks (I_d + Sigma_S)^-1
   */
  public selectOptimalRolloutSet(rollouts: RolloutPrefix[]): PruningSelectionResult {
    const startTime = performance.now();
    const N = rollouts.length;
    const { d, k, rho, regularizerTau } = this.config;

    if (k > N) {
      throw new Error(`Requested budget k (${k}) exceeds candidate count N (${N})`);
    }

    // 1. Ekstraksi vektor bobot lambda_i dan kappa_i untuk setiap rollout
    // Berdasarkan teorema: lambda_i(-1) = phi(-q_i) / Phi(-q_i), kappa_i(-1) = lambda_i * (lambda_i - q_i)
    const lambdas = new Float64Array(N);
    const kappas = new Float64Array(N);
    const logBaseFailures = new Float64Array(N);

    for (let i = 0; i < N; i++) {
      const q_i = rollouts[i].qualityScore ?? 0.0;
      const phiVal = gaussianPdf(-q_i);
      const cdfVal = Math.max(1e-12, gaussianCdf(-q_i));

      const lam = phiVal / cdfVal;
      lambdas[i] = lam;
      kappas[i] = lam * (lam - q_i);
      logBaseFailures[i] = Math.log(cdfVal);
    }

    // 2. Inisialisasi State Rekursif Matriks (I_d + Sigma_S)^-1
    // M = (I_d + Sigma_S)^-1, awalnya M = I_d
    // Representasi matriks d x d dalam Float64Array flat
    const invM = new Float64Array(d * d);
    for (let row = 0; row < d; row++) {
      invM[row * d + row] = 1.0;
    }

    // Vektor akumulasi b_S = sum_{i in S} (-lambda_i * h_i)
    const b_S = new Float64Array(d);
    let currentLogDet = 0.0; // log det(I_d + Sigma_S)
    let currentSumLogFail = 0.0;

    const selected: number[] = [];
    const remaining = new Set();
    for (let i = 0; i < N; i++) remaining.add(i);

    const surrogateScores: number[] = [];

    // 3. Iterasi Greedy Step k kali
    for (let step = 0; step < k; step++) {
      let bestCandidate = -1;
      let minDeltaLogLoss = Infinity;
      let bestRankOneV: Float64Array | null = null;
      let bestGamma = 0.0;

      for (const candIdx of remaining) {
        const h_cand = rollouts[candIdx].embedding;
        const kappa_cand = kappas[candIdx];
        const lam_cand = lambdas[candIdx];

        // Hitung v = M * h_cand
        const v = new Float64Array(d);
        for (let r = 0; r < d; r++) {
          let sum = 0.0;
          const rowOffset = r * d;
          for (let c = 0; c < d; c++) {
            sum += invM[rowOffset + c] * h_cand[c];
          }
          v[r] = sum;
        }

        // Inner product h_cand^T * v = h_cand^T * M * h_cand
        let h_M_h = 0.0;
        for (let r = 0; r < d; r++) {
          h_M_h += h_cand[r] * v[r];
        }

        const denom = 1.0 + kappa_cand * h_M_h;
        const deltaLogDet = Math.log(Math.max(1e-12, denom));

        // Hitung evaluasi marginal delta b_S^T * M_new * b_S_new
        // b_cand = b_S - lam_cand * h_cand
        const b_cand = new Float64Array(d);
        for (let r = 0; r < d; r++) {
          b_cand[r] = b_S[r] - lam_cand * h_cand[r];
        }

        // M_new = M - (kappa / denom) * (v * v^T)
        // b_cand^T * M_new * b_cand = b_cand^T * M * b_cand - (kappa / denom) * (b_cand^T * v)^2
        let b_M_b = 0.0;
        let b_dot_v = 0.0;
        for (let r = 0; r < d; r++) {
          let M_b_r = 0.0;
          const rowOffset = r * d;
          for (let c = 0; c < d; c++) {
            M_b_r += invM[rowOffset + c] * b_cand[c];
          }
          b_M_b += b_cand[r] * M_b_r;
          b_dot_v += b_cand[r] * v[r];
        }

        const quadraticPenalty = 0.5 * (b_M_b - (kappa_cand / denom) * b_dot_v * b_dot_v);
        const deltaObjective = logBaseFailures[candIdx] - 0.5 * deltaLogDet + quadraticPenalty;

        if (deltaObjective < minDeltaLogLoss) {
          minDeltaLogLoss = deltaObjective;
          bestCandidate = candIdx;
          bestRankOneV = v;
          bestGamma = kappa_cand / denom;
        }
      }

      if (bestCandidate === -1) break;

      // 4. Lakukan Rank-One Update pada M = (I_d + Sigma_S)^-1 secara in-place O(d^2)
      // Sherman-Morrison Formula: M_new = M - gamma * (v * v^T)
      const candIdx = bestCandidate;
      const v = bestRankOneV!;
      const gamma = bestGamma;
      const lam_cand = lambdas[candIdx];
      const h_cand = rollouts[candIdx].embedding;

      for (let r = 0; r < d; r++) {
        const rowOffset = r * d;
        const v_r = v[r];
        for (let c = 0; c < d; c++) {
          invM[rowOffset + c] -= gamma * v_r * v[c];
        }
      }

      // Update akumulator b_S
      for (let r = 0; r < d; r++) {
        b_S[r] -= lam_cand * h_cand[r];
      }

      selected.push(candIdx);
      remaining.delete(candIdx);
      currentSumLogFail += logBaseFailures[candIdx];
      surrogateScores.push(minDeltaLogLoss);
    }

    const elapsed = performance.now() - startTime;
    // Estimasi probabilitas pass@k = 1 - exp(total_surrogate_loss)
    const estimatedPass = 1.0 - Math.exp(Math.min(0, currentSumLogFail));

    return {
      selectedIndices: selected,
      estimatedPassAtK: Math.max(0.0, Math.min(1.0, estimatedPass)),
      executionTimeMs: elapsed,
      surrogateScoresByStep: surrogateScores,
    };
  }
}

7. Evaluasi Empiris Komparatif: 8 Model Penalaran Lintas AIME & Omni-MATH

Efektivitas PKTP dievaluasi secara masif melintasi delapan model penalaran terbuka (open-weight reasoning models) dalam dua kelompok skala parameter:

• Small Tier: Qwen3-0.6B, Qwen3-1.7B, OpenMath-Nemotron-1.5B, dan DeepSeek-R1-Distill-Qwen-1.5B.
• Large Tier: Qwen3-8B, OpenMath-Nemotron-7B, DeepSeek-R1-Distill-Qwen-7B, dan Skywork-OR1-Math-7B.

Seluruh model diuji pada gabungan problem matematika kompetisi tingkat tinggi: AIME 2024, 2025, 2026, HMMT 2024–2026, RIMO-N, AMO-Bench, serta Omni-MATH level 7 s/d 9. Konfigurasi inferensi menggunakan $N = 128$ rollout, pemangkasan pada cutoff $T = 4000$ token, dan budget final $B = 32{,}768$ token.

Hasil pengujian membuktikan bahwa keunggulan terbesar PKTP terjadi pada rentang budget moderat ($k = 2, 4, 8$). Pada rentang ini, Linear Probe mengalami degradasi tajam akibat korelasi kegagalan bersama (misalnya pada DeepSeek-R1-Distill-Qwen-7B, akurasi Linear Probe turun menjadi 46.7% di $k=2$, bahkan lebih buruk dari sampling acak 48.3%). Di sisi lain, RepExp menderita bias outlier (hanya mencapai 47.2%). PKTP secara konsisten mendominasi di angka 49.6% pada $k=2$ dan 59.7% pada $k=4$.

8. Rekomendasi Taktis Rekayasa Serving Infrastruktur Test-Time Reasoning 2026/2027

1. Ganti Heuristik Best-of-N dengan Early Cutoff Thought Pruning: Jangan membiarkan ratusan rollout berjalan hingga 32K token sebelum dievaluasi oleh Reward Model. Terapkan ambang pemangkasan awal pada $T = 3000 - 4000$ token dan eliminasi 80-90% kandidat terlemah di awal eksekusi.
2. Hindari Pemilihan Top-k Berdasarkan Probe Linear Saja: Menggunakan reward model atau probe linear untuk memilih top-$k$ solusi akan mengakibatkan sistem terjebak pada correlated failure modes. Satu kesimpulan salah pada premis awal akan menggugurkan seluruh armada rollout yang terpilih.
3. Terapkan PKTP Submodular Selector di Inference Router (vLLM / SGLang): Gunakan algoritma greedy rank-one update PKTP di level orchestration router. Dengan overhead komputasi kurang dari 5 milidetik, sistem serving dapat memangkas jutaan token generasi tanpa mengorbankan metrik $ ext{pass}@k$.
4. Sesuaikan Parameter Korelasi $ ho$ Berdasarkan Diversitas Problem: Pada problem penalaran deduktif ketat (seperti formal theorem proving di Lean 4), naikkan bobot korelasi $ ho$ untuk menekan redundansi langkah pembuktian. Pada tugas matematika berbasis pola, pertahankan $ ho$ moderat untuk menjaga eksploitasi lintasan nalar berprobabilitas tinggi.