Skip to content

CAS: Conformalized Agentic Search via Adaptive Retrieval and Policy Weighting

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/S1llyBird/CAS
Area: LLM Agent
Keywords: Agentic Search, Conformal Prediction, Adaptive Retrieval, Reinforcement Learning Fine-Tuning, Policy Weighting

TL;DR

Addressing the dual reliability crisis of retrieval noise and reinforcement learning overconfidence in search agents, CAS introduces Conformal Prediction into agentic search by employing Adaptive Prediction Sets (APS) for dynamic, coverage-guaranteed document truncation and Adaptive Conformal Inference (ACI) to penalize low-confidence trajectories during GRPO, substantially boosting multi-hop reasoning accuracy while curbing redundant tool calls.

Background & Motivation

The synergy between Large Language Models (LLMs) and external search engines has rapidly evolved from early static "retrieve-then-generate" paradigms (traditional RAG) into fully autonomous Agentic Search. In this formulation, agents interleave multi-step chain-of-thought reasoning with external information gathering within a single continuous generative trajectory, deciding when to query external sources, parsing observations, and adjusting conclusions on the fly. To unlock the full potential of autonomous reasoning in knowledge-intensive domains, reinforcement learning fine-tuningโ€”most prominently Group Relative Policy Optimization (GRPO)โ€”has become the standard approach for incentivizing effective tool-use and deliberation strategies.

However, fine-tuning search agents with reinforcement learning introduces a severe reliability crisis stemming from vulnerabilities on both the retrieval side and the training side. On the retrieval side, existing frameworks almost exclusively rely on heuristic, fixed Top-\(K\) document truncation. Given that user queries vary widely in intrinsic difficulty, a fixed cutoff is inherently maladaptive: for straightforward single-hop queries, a static window injects irrelevant distractor documents and induces context fragmentation or "lost in the middle" degradation; conversely, for intricate multi-hop questions, a rigid cutoff prematurely truncates vital bridge evidence, driving the agent to initiate frantic, redundant compensation searches. On the training side, standard RL fine-tuning with sparse binary rewards (such as exact string match) causes severe calibration collapse. As training progresses, policy models quickly become overconfident, generating hallucinated rationales and heavily reinforcing unconfident "lucky guesses," which locks the agent into loops of erratic, wasteful tool calls.

Because standard heuristic metrics lack formal finite-sample guarantees, and because continuous policy updates during reinforcement learning induce non-stationary distribution shifts that violate classical independent and identically distributed (i.i.d.) assumptions, a principled statistical framework capable of handling dynamic drift is urgently required. Core idea: Conformalized Agentic Search (CAS) introduces Conformal Prediction simultaneously into retrieval and policy optimization, utilizing Adaptive Prediction Sets (APS) to translate statistical coverage into query-dependent document truncation, while deploying Adaptive Conformal Inference (ACI) to track non-stationary policy drift and penalize low-confidence trajectories within GRPO, establishing an end-to-end statistically grounded, highly efficient search agent.

Method

Overall Architecture

The CAS architecture bridges internal cognitive deliberation with external retrieval environments under strict statistical coverage bounds. Guided by a structured reasoning grammar, the agent initiates reasoning within <think>...</think> tags upon receiving a prompt. When encountering an informational bottleneck, it halts generation and emits a concise query enclosed in <search>...</search> tags. Instead of returning an arbitrary number of documents, the retrieval backend dynamically sizes the candidate pool using an Adaptive Prediction Set (APS) module that ensures a marginal coverage guarantee of at least \(1 - \alpha_{\text{APS}}\), returning the compact subset inside <information>...</information> tags for subsequent reflection. This cycle iterates until the agent produces a definitive prediction inside <answer>...</answer> tags. On the training side, rollout trajectories are evaluated using answer token negative log-likelihood (NLL) as non-conformity scores. The Adaptive Conformal Inference (ACI) module dynamically tracks coverage performance over a rolling window to update an empirical quantile threshold, modulating GRPO advantage updates by discounting uncertain trajectories to prevent overconfident hallucinations and lucky guesses.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Query and Group Rollouts<br/>Structured reasoning grammar"] --> B["Adaptive Prediction Set Retrieval Truncation<br/>Dynamic softmax probability accumulation"]
    B --> C["Exponentially Smoothed Adaptive Conformal Inference<br/>Tracking rolling NLL quantiles under policy drift"]
    C --> D["Confidence-Aware Policy Loss Weighting<br/>Discounting low-confidence lucky guesses in GRPO"]
    D --> E["Optimized High-Reliability Search Policy<br/>Suppressed redundant searches and hallucinations"]

Key Designs

1. Adaptive Prediction Set Retrieval Truncation: Sizing External Evidence Sets Dynamically under Marginal Coverage Guarantees

Traditional search agents employ static Top-\(K\) document retrieval, failing to adapt to query-specific difficulty and thus introducing distracting noise into easy questions or omitting crucial evidence in complex multi-step reasoning. To establish a rigorous statistical bound on retrieved knowledge, CAS applies the Adaptive Prediction Set (APS) method to external dense retrieval. Upon receiving candidate documents \(D = \{d_1, \dots, d_n\}\) with raw similarity scores from an external dense retriever (E5-base-v2), the module normalizes these scores via a softmax operator into relevance probabilities \(p(d_i \mid q)\). Documents are sorted descendingly, and the algorithm identifies the minimum cutoff index \(k\) such that the cumulative mass first meets or exceeds a pre-calibrated threshold \(\hat{q}_{\text{APS}}\):

\[\sum_{i=1}^k p(d_i \mid q) \ge \hat{q}_{\text{APS}}\]

This yields an adaptive subset \(D_{\text{APS}} = \{d_1, \dots, d_k\}\). For unambiguous factual queries, the probability concentrates rapidly, returning a concise set of 1 to 2 documents; for ambiguous or intricate queries, the set automatically expands to include all plausibly relevant supporting facts. Crucially, this provides a formal finite-sample marginal coverage guarantee \(P(Y_{\text{test}} \in C(X_{\text{test}})) \ge 1 - \alpha_{\text{APS}}\), preventing hallucination cascades caused by missing evidence while shielding the context window from redundant distractors.

2. Exponentially Smoothed Adaptive Conformal Inference: Tracking Answer-Level Uncertainty Across Evolving Policy Distributions

Standard Conformal Prediction fundamentally assumes exchangeable, identically distributed data. In reinforcement learning, however, the policy model \(\pi_\theta\) updates continuously, causing non-stationary distribution shifts that invalidate static conformal bounds; additionally, binary reward signals severely degrade model calibration. CAS resolves this by adapting Adaptive Conformal Inference (ACI) to monitor generation uncertainty online. For each trajectory \(y_i\) generated for input \(x_t\), CAS computes its non-conformity score \(s(x_t, y_i)\) as the average Negative Log-Likelihood (NLL) of the token sequence generated exclusively within <answer>...</answer> tags:

\[s(x_t, y_i) = \frac{1}{|M_i|} \sum_{j \in M_i} \left( -\log \pi_\theta(y_j \mid y_{<j}, x_t) \right)\]

To suppress volatile batch-to-batch fluctuations, CAS updates the time-varying error rate \(\alpha_t\) using an exponentially weighted moving average over past empirical miscoverages: \(\alpha_{t+1} = \alpha_t + \gamma (\rho - \sum_{s=1}^t v_s \text{err}_s)\), where \(v_s \propto 0.95^{t-s}\). A dynamic quantile threshold \(\hat{q}_t = \hat{Q}_t(1 - \alpha_t)\) is evaluated over a sliding calibration window of the 2,000 most recent scores. If recent trajectories slip outside the predicted confidence bound, the quantile threshold automatically expands, dynamically adapting error tolerance to distribution shifts without making restrictive parametric assumptions.

3. Confidence-Aware Policy Loss Weighting: Synergizing Advantage Estimates to Penalize Low-Confidence Lucky Guesses

Standard RL objectives treat any trajectory that matches ground-truth strings equally, aggressively reinforcing unconfident guesses that hit the right token sequence by pure chance. To prevent the policy from internalizing spurious reasoning paths, CAS couples the dynamic ACI threshold \(\hat{q}_t\) with the GRPO optimization objective. For each rollout trajectory \(y_i\) in a sampled group of size \(G\), a dynamic confidence weight \(\omega_i\) is assigned: if \(s(x_t, y_i) \le \hat{q}_t\), the trajectory is deemed reliable and assigned full weight \(\omega_i = 1\); if \(s(x_t, y_i) > \hat{q}_t\), it is categorized as low confidence and discounted by \(\omega_i = \eta\) (set to \(\eta = 0.5\)). The policy objective is formulated as:

\[\mathcal{L}_{\text{GRPO}}(\theta) = \mathbb{E} \left[ \frac{1}{G} \sum_{i=1}^G \omega_i \mathcal{L}_{\text{clip}, i}(\theta) - \beta D_{\text{KL}}(\pi_\theta \parallel \pi_{\text{ref}}) \right]\]

This mechanism acts as a dual-constraint filter alongside the group-normalized relative advantage \(A_i\). When a trajectory is an unconfident guess (\(A_i > 0\) yet \(s(x_t, y_i) > \hat{q}_t\)), the positive gradient update is halved by \(\eta\), neutralizing reward hacking. Conversely, when the agent is confidently incorrect (\(A_i < 0\) and \(s(x_t, y_i) \le \hat{q}_t\)), the full penalty (\(\omega_i = 1\)) is enforced to aggressively discourage overconfident errors, steering the policy strictly toward verified, high-confidence reasoning trajectories.

A Worked Example

Consider the multi-hop query: "Which hockey team does the younger brother of Sean James Pronger currently work for?" 1. Initial Deliberation & Sub-query Generation: The agent identifies two essential hops in <think>: finding Sean James Pronger's younger brother, followed by identifying his current employer. It emits <search> Sean James Pronger younger brother </search>. 2. Dynamic Context Truncation: Because the relationship query involves several historical references, APS dynamically accumulates relevance mass and retains 4 documents (confirming Chris Pronger as Sean's younger brother who joined him at Bowling Green State University), while pruning dozens of irrelevant hockey news articles. 3. Targeted Bridge Lookup: In the second hop, the agent issues <search> Chris Pronger current team </search>. 4. Focused Retrieval & Answer Output: Given the focused query, document scores concentrate sharply; APS returns only 2 high-scoring passages stating that Chris Pronger serves as senior advisor of hockey operations for the Florida Panthers. The agent immediately terminates searching and outputs <answer> Florida Panthers </answer>. 5. Training Verification: The answer token NLL falls well below the active ACI threshold \(\hat{q}_t\). Because both accuracy and confidence align, the trajectory receives a full weight of \(\omega_i = 1.0\) under GRPO. Had the agent guessed "Florida Panthers" during the first turn without searching, the elevated NLL would have triggered the \(\eta = 0.5\) discount, preventing the model from learning to bypass retrieval.

Loss & Training

The reward function combines accuracy and formatting constraints: \(r(x, y) = r_{\text{acc}} + r_{\text{fmt}}\). The accuracy reward is binary exact match \(r_{\text{acc}} = \text{EM}(a_{\text{pred}}, a_{\text{gold}}) \in \{0, 1\}\). The format reward is scaled by \(\gamma_{\text{fmt}} = 0.2\): \(r_{\text{fmt}}(y) = 0.2 \cdot [-r_{\text{acc}}(1 - I_{\text{valid}}) + (1 - r_{\text{acc}})(I_{\text{valid}} + 0.5 I_{\text{ans}}(1 - I_{\text{valid}}))]\). Training operates under the VeRL distributed framework using PyTorch and Ray across 4 RTX PRO 6000 GPUs. Policy models are trained with a rollout group size of \(G = 5\), sampling 512 prompts per global step, with interaction rounds capped at 4. The Actor learning rate is set to \(1 \times 10^{-6}\) with a warmup ratio of 0.285, the Critic learning rate is \(1 \times 10^{-5}\), and the KL penalty coefficient is \(\beta = 0.001\). ACI employs step size \(\gamma = 0.005\), target error rate \(\rho = 0.25\), and discount factor \(\eta = 0.5\). APS operates with significance level \(\alpha_{\text{APS}} = 0.20\) and softmax temperature 0.01.

Key Experimental Results

Main Results

The authors evaluate CAS across seven benchmark question answering datasets spanning both single-hop tasks (NQ, TriviaQA, PopQA) and complex multi-hop reasoning tasks (HotpotQA, 2WikiMultiHopQA, Musique, Bamboogle) using the Exact Match (EM) metric.

Method Backbone General QA Avg Multi-Hop QA Avg Overall Average EM
Direct Inference - 0.167 0.109 0.134
Chain-of-Thought (CoT) - 0.020 0.011 0.015
Standard RAG - 0.426 0.152 0.270
IRCoT - 0.208 0.161 0.181
Search-o1 - 0.324 0.203 0.255
Supervised Fine-Tuning (SFT) - 0.215 0.147 0.176
Rejection Sampling - 0.371 0.186 0.265
Search-R1 Qwen2.5-3B-Instruct 0.451 0.249 0.336
CAS (Ours) Qwen2.5-3B-Instruct 0.498 0.328 0.401 (+0.065)
Search-R1 Qwen3-8B 0.496 0.329 0.400
Search-R2 (Closed-source baseline) Qwen3-8B 0.540 0.375 0.446
CAS (Ours) Qwen3-8B 0.541 0.407 0.464 (+0.018)

Detailed per-dataset results demonstrate consistent improvements. On Qwen3-8B, CAS achieves 0.490 on NQ (vs. 0.440 for Search-R1), 0.668 on TriviaQA, 0.465 on PopQA, 0.463 on HotpotQA (vs. 0.372 for Search-R1), 0.431 on 2WikiMultiHopQA, 0.213 on Musique (vs. 0.157 for Search-R1), and 0.520 on Bamboogle.

Ablation Study

Component-wise ablations and sensitivity analyses conducted on Qwen2.5-3B-Instruct reveal the distinct contribution of each mechanism:

Configuration / Variant General QA Avg Multi-Hop QA Avg Overall Average EM Observation / Note
CAS Full Model (Default) 0.498 0.328 0.401 Full framework (\(\rho = 0.25, \alpha_{\text{APS}} = 0.20\))
w/o ACI Weighting (-ACI) 0.481 0.311 0.384 Loss of uncertainty guidance; overconfidence triggers hallucinations (-0.017)
w/o Adaptive Truncation (-APS) 0.490 0.313 0.389 Fallback to fixed Top-3; noise in single-hop and missing evidence in multi-hop
Lenient Filtering \(\rho = 0.10\) 0.497 0.302 0.386 Only 10% trajectories discounted; insufficient confidence constraint
Aggressive Filtering \(\rho = 0.40\) 0.495 0.273 0.368 40% trajectories discounted; over-penalization dilutes valid RL reward
Aggressive Truncation \(\alpha_{\text{APS}} = 0.35\) 0.476 0.294 0.372 Returns 2.4 docs on average; critical facts frequently omitted
Broad Retrieval Window \(\alpha_{\text{APS}} = 0.05\) 0.504 0.234 0.350 Returns 4.8 docs on average; excessive context noise cripples multi-hop reasoning

Key Findings

  • Synergistic Dual Constraints: Disabling either module degrades overall accuracy to 0.384 (-ACI) and 0.389 (-APS). Tracking tool-call frequencies reveals that without ACI, search calls fluctuate violently (averaging nearly 2.0 calls per question), driven by overconfident hallucinations or uncalibrated secondary verification queries. Disabling APS similarly elevates search frequencies as the agent attempts to compensate for truncated evidence.
  • Robustness Under Non-stationary RL Drift: At the onset of RL training (steps 0-20), policy shifts cause an abrupt spike in low-confidence samples. ACI's dynamic update rule successfully tracks this surge and stabilizes \(\alpha_t\) to the target rate \(\rho = 0.25\), demonstrating that static conformal bounds would fail under distribution shift.
  • Sensitivity to Context Window Noise: Lowering \(\alpha_{\text{APS}}\) to 0.05 expands the average retrieved set to 4.8 documents, raising single-hop accuracy to 0.504 but causing multi-hop performance to collapse to 0.234 due to distracting context noise. The default \(\alpha_{\text{APS}} = 0.20\) (averaging 3.4 documents) achieves the optimal trade-off between coverage and noise suppression.

Highlights & Insights

  • Conformal Prediction in Interactive Agent Environments: Rather than relying on unreliable verbalized confidence scores, CAS provides the first theoretically grounded framework that incorporates finite-sample coverage guarantees into both retrieval truncation and policy optimization.
  • Taming RL Lucky Guesses via Advantage-Confidence Synergy: By scaling GRPO clipped objectives with an ACI-derived indicator, the method discounts unconfident accidental successes while enforcing maximum penalties on confident blunders, dramatically stabilizing exploration.
  • Adaptive Context Sizing Minimizes Computational Overhead: APS trims irrelevant documents dynamically based on softmax probability concentration, reducing average retrieval length to 3.4 documents while preserving valid statistical coverage.

Limitations & Future Work

  • Evaluation Limited to General Knowledge QA: While highly effective on Wikipedia-scale open-domain benchmarks, CAS has not yet been validated on specialized domains (e.g., code evolution, legal reasoning, clinical healthcare) where retriever calibration may behave differently.
  • Teacher Model Dependency for Calibration: Constructing the initial multi-hop calibration queries and golden evidence indices relies on an external teacher model (DeepSeek-V3.2), which may be challenging in completely self-contained offline environments.
  • Outcome-Only Conformal Guarantees: CAS quantifies confidence purely on final answer tokens; extending conformal guarantees to intermediate reasoning steps (process reliability) remains an open challenge.
  • vs. Search-R1 / Search-R2: Search-R1 uses fixed Top-\(K\) retrieval and unconstrained GRPO, suffering from overconfidence and high tool redundancy; Search-R2 introduces an auxiliary actor-refiner framework that increases architectural complexity. CAS achieves higher accuracy within a streamlined single-agent framework using statistical conformal control.
  • vs. Adaptive-RAG / Search-o1: Adaptive-RAG relies on an explicit query-complexity classifier that is prone to out-of-distribution classification errors. Search-o1 incorporates heavy test-time reasoning and verification loops. CAS dynamically adjusts retrieval within a unified generative trajectory with mathematical coverage guarantees.

Rating

  • Novelty: โญโญโญโญโญ Pioneering application of Conformal Prediction and Adaptive Conformal Inference to reinforcement-learning-tuned search agents.
  • Experimental Thoroughness: โญโญโญโญโญ Evaluated across seven diverse QA benchmarks with deep ablation studies on training dynamics and parameter sensitivity.
  • Writing Quality: โญโญโญโญโญ Rigorous mathematical formulations, clear motivation, and complete algorithmic transparency.
  • Value: โญโญโญโญโญ Provides a principled foundation for resolving reliability, calibration collapse, and efficiency bottlenecks in autonomous tool-using agents.