KnowGPO (arXiv:2610.22331): Knowledge-Grouped Policy Optimization, Dekomposisi Kondisi Atomik, dan Eliminasi Noise Observasi pada Deep Search Agents

1. Anatomi Kegagalan GRPO & Process Supervision Konvensional pada Deep Search

Dalam skenario pencarian mendalam berhorizon panjang (long-horizon multi-turn search), sebuah agen AI dapat mengambil antara 10 hingga 30 langkah interaksi sebelum mengeluarkan jawaban final. Interaksi ini melibatkan pemanggilan search engine API, penjelajahan halaman dokumen HTML yang panjang dan berantakan, ekstraksi kutipan, hingga sintesis penalaran. Pendekatan pelatihan RL dominan saat ini menemui jalan buntu pada dua kubu:

• Outcome-Only RL (GRPO / RLVR): Algoritma seperti GRPO (yang dipopulerkan oleh DeepSeekMath dan DeepSeek-R1) hanya memberikan sinyal biner tunggal di ujung trajektori: $R(\tau) \in \{0, 1\}$. Kelemahan fatalnya adalah credit dilution: jika agen melakukan 15 langkah penelusuran brilian namun salah mengetik format di langkah ke-16, seluruh langkah brilian tersebut dihukum dengan penalti yang sama. Sebaliknya, jika agen melakukan penelusuran acak yang beruntung menemukan jawaban karena redundansi web, langkah-langkah sia-sia tersebut justru diperkuat.
• Surface Observation Grouping (GiGPO): Upaya memberikan pengawasan tingkat langkah (step-level supervision) sebelumnya mencoba mengelompokkan trajektori yang mengunjungi "state lingkungan yang sama" menggunakan kesamaan representasi embedding teks (misal cosine similarity BGE-large > 0.9). Pada deep search, metode ini runtuh total: dokumen web bersifat terbuka dan heterogen. Dari evaluasi empiris pada 5.922 trajektori nyata, pengelompokan observasi menghasilkan 79.4% singleton groups (hanya 51.8% langkah yang berhasil disejajarkan). Akibatnya, perbandingan keuntungan di dalam grup terdegenerasi menjadi perbandingan satu langkah dengan dirinya sendiri ($A = 0$).
• Internal Confidence Anchoring (IGPO): Pendekatan lain mencoba menghitung reward langkah dari lonjakan probabilitas internal model terhadap jawaban benar. Namun, sinyal keyakinan internal ini sangat rapuh terhadap bias konteks dokumen web yang panjang dan bising, kerap memicu halusinasi kepastian semu sebelum bukti yang cukup ditemukan.

GAMBAR 1: Arsitektur Menyeluruh KnowGPO (arXiv:2610.22331). Sisi Kiri: Dekomposisi kueri 2-tahap menghasilkan kondisi pengetahuan atomik terbumikan. Sisi Kanan: Rollout trajektori dikelompokkan berdasarkan kesamaan status pengetahuan monotonik $s_{i,t-1}$, di mana advantage dihitung dari incremental knowledge gain per langkah.

2. Abstraksi Status Pengetahuan: Dekomposisi Dua Tahap & Bitmask Monotonik

Terobosan kunci KnowGPO adalah mengabstraksikan progres pencarian bukan dari representasi teks observasi permukaan yang berfluktuasi, melainkan dari himpunan kondisi pengetahuan relevan yang berhasil diverifikasi.

A. Pipeline Dekomposisi Dua Tahap (Two-Stage Construction)

Untuk setiap kueri $Q$ dengan jawaban referensi $y^*$, KnowGPO membentuk himpunan kondisi pengetahuan atomik terhingga:

di mana masing-masing $k_j$ merepresentasikan kendala faktual tunggal (single-hop fact) yang mutlak diperlukan untuk menarik kesimpulan logis ke $y^*$. Konstruksi ini dijalankan melalui dua tahap:

1. Stage 1 — Ekstraksi Skeleton Penalaran: Mengidentifikasi rantai logika implisit dari kueri $Q$ dengan menyematkan placeholder untuk entitas yang belum diketahui, misalnya: {<E0> menyelenggarakan konser <E1>}, {<E1> diproduksi oleh perusahaan <E2>}, {<E0> adalah pendiri <E2>}.
2. Stage 2 — Pembumian Placeholder (Grounding): Membumikan entitas placeholder menggunakan jawaban ground truth $y^*$ dan trajektori referensi yang sukses, mengikat <E0> ke "Landy Chang", <E1> ke "Rock China Power", dan <E2> ke "Magic Stone Culture".

B. Akumulasi State Monotonik Terhadap Noise Verifier

Pada setiap langkah $t$ dari trajektori $\tau_i$, model verifier berbasis LLM (menggunakan DeepSeek-v3.2) memeriksa apakah observasi baru $o_{i,t}$ memenuhi satu atau beberapa kondisi $k_j$, menghasilkan vektor inkremen biner $\Delta s_{i,t} \in \{0, 1\}^K$:

Status pengetahuan kumulatif kemudian diakumulasikan secara monotonik melalui operasi bitwise OR:

Sifat monotonik ini krusial: fakta yang telah diperoleh agen di langkah sebelumnya tidak boleh hilang hanya karena halaman web di langkah berikutnya tidak lagi menampilkannya. Hal ini secara efektif menyerap transient noise dari verifier dan menjamin stabilitas semantik sepanjang puluhan langkah pencarian.

3. Mekanisme Pelatihan: Knowledge-Grouped Credit Assignment & Formulasi Keuntungan

Setelah ruang status didefinisikan secara semantik, KnowGPO membagi penghitungan keuntungan (advantage) ke dalam dua tingkat yang saling melengkapi:

A. Keuntungan Tingkat Episode (Global Task Alignment)

Dari $N$ trajektori yang di-sample untuk kueri yang sama, keuntungan tingkat episode dihitung persis seperti formulasi GRPO standar:

Komponen ini memastikan optimasi tetap terarah ke tujuan akhir dan mencegah agen terjebak dalam perilaku mengumpulkan informasi lokal (over-collecting loop) tanpa pernah menyelesaikan jawaban.

B. Keuntungan Tingkat Langkah Berbasis Partisi Pengetahuan (Local Epistemic Advantage)

Langkah-langkah non-terminal dari seluruh $N$ trajektori dipartisi ke dalam kelompok pengetahuan $G(\tilde{s})$. Dua langkah hanya dimasukkan ke dalam grup yang sama jika dan hanya jika keduanya memulai aksi dari status pengetahuan yang persis identik:

Reward proses didefinisikan sebagai perolehan pengetahuan inkremental (incremental knowledge gain):

Keuntungan tingkat langkah $A_{i,t}^S$ kemudian dinormalisasi di dalam kelompok $\mathcal{G}(\tilde{s})$:

Konstruksi ini menghasilkan perbandingan yang adil: langkah yang diambil agen dinilai relatif terhadap alternatif aksi yang dapat diambil dari posisi epistemik yang sama, bukan dibandingkan dengan langkah di fase pencarian lain yang berbeda konteks pengetahuannya.

C. Penggabungan Dual-Objective & Optimasi PPO Terpotong

Kedua sinyal keuntungan digabungkan dengan koefisien pencampuran $\omega = 0.3$:

Kebijakan $\pi_\theta$ kemudian dioptimalkan menggunakan fungsi objektif clipped surrogate PPO dengan penalti divergensi KL terhadap model referensi $\pi_{\text{ref}}$:

4. Pembuktian Empiris: Menyamai Model 32B pada Skala 8B

Peneliti mengevaluasi KnowGPO pada tiga benchmark pencarian mendalam paling berat di industri: BrowseComp-ZH, GAIA (General AI Assistants), dan Xbench-2505 / Xbench-2510. Seluruh model open-source yang dilatih menggunakan basis bobot identik (Qwen3-8B dengan ekspansi konteks YaRN 128K tokens).

GAMBAR 2: Kurva Akurasi Validasi Xbench-2505 sepanjang langkah pelatihan RL. KnowGPO membuka keunggulan signifikan mulai step 20 dan stabil di ~50%.

GAMBAR 3: Perincian waktu komputasi per iterasi RL. Verifikasi status pengetahuan dan grouping hanya menambah overhead komputasi < 3% dibanding GRPO standar.

5. Analisis Mekanistik: Mengapa Status Pengetahuan Jauh Lebih Unggul dari Observasi?

Eksperimen diagnostik pada 5.922 trajektori (55.571 total langkah penelusuran) membedah penyebab empiris di balik dominasi KnowGPO atas metode pengelompokan lainnya:

Data di atas menunjukkan fakta fundamental dalam rekayasa agen:

• Eliminasi Fenomena Singleton: Dengan knowledge state, 97.8% langkah berada di dalam grup non-singleton dengan rata-rata 3.88 trajektori berbeda per grup. Artinya, keuntungan dihitung dari perbandingan multi-agen yang kaya, bukan perbandingan kosong.
• Ablasi Reward Formula: Mengganti incremental gain $r_t$ dengan discounted future return $G_t$ ala GiGPO menurunkan akurasi hingga 6.0% di BrowseComp-ZH. Mengapa? Karena $G_t$ mengikat kredit langkah saat ini ke seluruh variansi acak di masa depan, sementara incremental gain memberikan sinyal lokal instan yang terbumikan ke fakta nyata.
• Nilai Optimal Omega: Pengujian parameter membuktikan $\omega = 0.3$ memberikan keseimbangan optimal. Memberikan bobot berlebih pada proses ($\omega = 0.5$) justru merusak konvergensi karena agen menjadi terlalu terobsesi mengumpulkan potongan informasi parsial dan melupakan batas waktu inferensi.

6. Implementasi TypeScript Produksi: Engine Partisi State & Perhitungan Advantage

Berikut adalah implementasi clean-architecture dari KnowGPO Engine dalam TypeScript yang dapat langsung disematkan pada runtime orkestrasi pencarian agen cerdas:

// Production Implementation: KnowGPO Knowledge State Engine & Grouped Advantage Calculator
// Berdasarkan formulasi formal arXiv:2610.22331 (Zhejiang University & Tencent, EMNLP 2026)
// Mengimplementasikan:
// 1. Two-Stage Atomic Knowledge Decomposition Tracker
// 2. Monotonic Binary Knowledge State Accumulator: s_{i,t} = s_{i,t-1} OR Delta s_{i,t}
// 3. Knowledge-Group Partitioning: G(s) = {(i, t) | s_{i,t-1} = s, a_{i,t} != answer}
// 4. Grounded Step-Level Reward & Group-Relative Advantage Normalization
// 5. Dual-Objective Advantage Blending: A_{i,t} = (1 - omega) * A_i^E + omega * A_{i,t}^S

export interface AtomicKnowledgeCondition {
  id: string; // k_j
  description: string;
  stage1Skeleton: string;
  groundedEntities: Record<string, string>; // { "<E0>": "Landy Chang", "<E1>": "Magic Stone" }
}

export interface StepObservation {
  turnIndex: number;
  action: 'search' | 'browse' | 'click' | 'answer';
  actionQuery?: string;
  rawObservation: string;
}

export interface TrajectoryStepRecord {
  episodeId: string;
  stepIndex: number;
  action: 'search' | 'browse' | 'click' | 'answer';
  observation: string;
  priorKnowledgeState: boolean[]; // s_{i,t-1}
  newKnowledgeDelta: boolean[];    // Delta s_{i,t}
  cumulativeKnowledgeState: boolean[]; // s_{i,t}
  incrementalGain: number;       // ||s_{i,t}||_1 - ||s_{i,t-1}||_1
  stepAdvantage?: number;        // A_{i,t}^S
  finalAdvantage?: number;       // A_{i,t}
}

export class KnowGPOEngine {
  private conditions: AtomicKnowledgeCondition[] = [];
  private readonly omega: number; // Mixing coefficient (default 0.3)
  private readonly epsilon: number = 1e-6;

  constructor(conditions: AtomicKnowledgeCondition[], omega: number = 0.3) {
    this.conditions = conditions;
    this.omega = omega;
  }

  /**
   * 1. Monotonic Knowledge State Accumulation (Eq. 2 & Eq. 3)
   * Menyerap noise transien verifier dan memastikan pengetahuan tidak terhapus
   */
  public updateKnowledgeState(
    priorState: boolean[],
    newDelta: boolean[]
  ): { nextState: boolean[]; gain: number } {
    const K = this.conditions.length;
    const nextState = new Array(K).fill(false);
    let priorCount = 0;
    let nextCount = 0;

    for (let j = 0; j < K; j++) {
      if (priorState[j]) priorCount++;
      // Monotonic OR operator: s_{i,t} = s_{i,t-1} lor Delta s_{i,t}
      nextState[j] = priorState[j] || (newDelta[j] ?? false);
      if (nextState[j]) nextCount++;
    }

    const gain = nextCount - priorCount; // r_{i,t} = ||s_{i,t}||_1 - ||s_{i,t-1}||_1
    return { nextState, gain };
  }

  /**
   * Mengubah vektor boolean ke representasi state hashable untuk grouping
   */
  public getStateKey(state: boolean[]): string {
    return state.map(b => (b ? '1' : '0')).join('');
  }

  /**
   * 2. Knowledge-Grouped Credit Assignment (Eq. 4 s.d. Eq. 8)
   * Mengelompokkan langkah berdasarkan state awal yang sama dan menghitung advantage
   */
  public computeGroupedAdvantages(
    episodes: {
      episodeId: string;
      steps: {
        action: 'search' | 'browse' | 'click' | 'answer';
        observation: string;
        deltaVerified: boolean[];
      }[];
      isSuccess: boolean;
    }[]
  ): TrajectoryStepRecord[] {
    const N = episodes.length;
    const K = this.conditions.length;

    // A. Hitung Episode-Level Advantage A_i^E (GRPO Outcome Normalization)
    const outcomeRewards = episodes.map(ep => (ep.isSuccess ? 1.0 : 0.0));
    const meanOutcome = outcomeRewards.reduce((a, b) => a + b, 0) / N;
    const varOutcome = outcomeRewards.reduce((a, b) => a + Math.pow(b - meanOutcome, 2), 0) / N;
    const stdOutcome = Math.sqrt(varOutcome);

    const episodeAdvantages = outcomeRewards.map(r => (r - meanOutcome) / (stdOutcome + this.epsilon));

    // B. Rollout lintasan dan ekstrak monotonic state per step
    const allStepRecords: TrajectoryStepRecord[] = [];
    // Map untuk mengelompokkan langkah: stateKey -> Array of reference records
    const knowledgeGroups = new Map<string, TrajectoryStepRecord[]>();

    episodes.forEach((ep, epIdx) => {
      let currentState = new Array(K).fill(false);

      ep.steps.forEach((step, stepIdx) => {
        const priorState = [...currentState];
        const { nextState, gain } = this.updateKnowledgeState(priorState, step.deltaVerified);
        currentState = nextState;

        const record: TrajectoryStepRecord = {
          episodeId: ep.episodeId,
          stepIndex: stepIdx,
          action: step.action,
          observation: step.observation,
          priorKnowledgeState: priorState,
          newKnowledgeDelta: step.deltaVerified,
          cumulativeKnowledgeState: currentState,
          incrementalGain: gain,
        };

        allStepRecords.push(record);

        // Abaikan langkah terminal 'answer' dari process grouping (Eq. 5)
        if (step.action !== 'answer') {
          const groupKey = this.getStateKey(priorState);
          if (!knowledgeGroups.has(groupKey)) {
            knowledgeGroups.set(groupKey, []);
          }
          knowledgeGroups.get(groupKey)!.push(record);
        }
      });
    });

    // C. Normalisasi Step-Level Advantage A_{i,t}^S di dalam masing-masing grup G(s)
    knowledgeGroups.forEach((groupSteps, stateKey) => {
      const gains = groupSteps.map(s => s.incrementalGain);
      const groupMean = gains.reduce((a, b) => a + b, 0) / groupSteps.length;
      const groupVar = gains.reduce((a, b) => a + Math.pow(b - groupMean, 2), 0) / groupSteps.length;
      const groupStd = Math.sqrt(groupVar);

      groupSteps.forEach(stepRec => {
        // Jika ukuran grup 1 (singleton) atau std == 0, advantage = 0
        if (groupSteps.length <= 1 || groupStd < 1e-7) {
          stepRec.stepAdvantage = 0.0;
        } else {
          stepRec.stepAdvantage = (stepRec.incrementalGain - groupMean) / (groupStd + this.epsilon);
        }
      });
    });

    // D. Gabungkan Episode-Level dan Step-Level Advantage (Eq. 8)
    const epAdvMap = new Map<string, number>();
    episodes.forEach((ep, idx) => {
      epAdvMap.set(ep.episodeId, episodeAdvantages[idx]);
    });

    allStepRecords.forEach(stepRec => {
      const epAdv = epAdvMap.get(stepRec.episodeId) ?? 0.0;
      const stepAdv = stepRec.stepAdvantage ?? 0.0;

      // Pada langkah terminal 'answer', gunakan 100% episode advantage
      if (stepRec.action === 'answer') {
        stepRec.finalAdvantage = epAdv;
      } else {
        stepRec.finalAdvantage = (1.0 - this.omega) * epAdv + this.omega * stepAdv;
      }
    });

    return allStepRecords;
  }
}

7. Rekomendasi Praktis untuk Insinyur AI & Pengembang Sistem Autonomous Search

Penelitian ini menyuguhkan prinsip arsitektur mutlak yang wajib diadopsi dalam merancang platform Deep Research dan AI Agents generasi berikutnya:

1. Tinggalkan Pengelompokan Berbasis Teks Permukaan: Jangan pernah mencoba menyelaraskan trajektori penelusuran agen menggunakan embedding dokumen atau URL. Variasi crawling web terlalu dinamis. Petakan selalu dokumen ke dalam bitmask kondisi informasi yang telah terverifikasi.
2. Terapkan Akumulasi Status Monotonik: Gunakan operasi bitwise OR ($s_t = s_{t-1} \lor \Delta s_t$) untuk melacak pemenuhan kondisi. Ini adalah peredam noise terbaik untuk mengatasi fluktuasi output model verifier atau ketidakkonsistenan ekstraksi teks.
3. Gunakan Dual-Objective Blending (70/30): Pertahankan 70% bobot untuk outcome-level advantage ($1 - \omega = 0.7$) dan 30% untuk step-level knowledge gain ($\omega = 0.3$). Kombinasi ini memberikan densitas supervisi optimal tanpa kehilangan visi penyelesaian akhir tugas.
4. Hemat Biaya Komputasi dengan Single-Stage RL: Dengan overhead komputasi kurang dari 3% di atas GRPO standar, KnowGPO membuktikan bahwa model 8B dapat menandingi model 32B open-source tanpa memerlukan dataset kepemilikan berbayar atau infrastruktur server reward model yang rumit.