HERALD: Counterfactual Audits and Minimal Repairs for Proof-of-Retrieval Rewards

The paper addresses the problem of reward design for search-agent reinforcement learning. As stated in the abstract: Search-agent rewards mix answer quality, citation grounding, tool cost, and anti-hacking terms; a high score therefore need not imply that cited evidence was retrieved, and added penalties can cancel. The authors note that decomposed rewards (answer correctness, evidence support, citation format, tool cost, action validity) are convenient because scores can be replayed offline, but this "also creates substitution opportunities: answer reward can compensate for a broken retrieval trace, tool-cost savings can offset an anti-hacking term, and an annotation proxy can penalize a reasonable original more than an edited attack."

The authors identify three design mistakes that make auditing rewards difficult: "(i) an edit that changes search, answer, and citations at once does not isolate proof of retrieval; (ii) reporting zero attacks without an eligibility denominator or a nonzero upper bound overstates certainty; (iii) comparing a base reward only with a large detector bundle cannot reveal whether one check suffices or whether the bundle creates penalty cancellation."

HERALD treats a reward as a program under paired adversarial unit test. Its role is as an early-warning audit that exposes reward loopholes before policy optimization. It: "(i) constructs same-question structural interventions; (ii) records exactly which fields and labels each operator can access; (iii) conditions on attack eligibility and detector isolation; (iv) reports both attack success and paired reward margin; and (v) enumerates the full detector lattice."

Key design principles:

• Information boundary: "Candidate generation reads only the question, logged trajectory, and corpus. Candidate-visible refers only to generation; reward-maximizing selection is an oracle-selected offline upper bound whenever the score reads gold-derived terms." Oracle-only fields include gold answer, support IDs, and EM/evaluation labels.

• Eligibility and isolation: An attack is eligible only if its target detector is false on the original and true on the edit. It is isolated when unrelated visible flags do not change. The operator target sets are D same = U, D launder = L, D fake = F. Primary tables use isolated-eligible subsets... preventing a zero caused by attacking already-invalid originals.

• Paired estimands: The paired margin is M R(A, τ) = R(A(τ), x) − R(τ, x) and the attack-success rate is ASR R(A) = E[⊮ M R(A, τ) ≥ 0]. Ties count as attacks. Questions, not trajectory rows, are the sampling unit... We use 5,000 deterministic question-cluster bootstrap replicates. For zero events, they report the one-sided exact 95% upper bound 1 − 0.05(1/n) rather than a degenerate interval.

• Complete detector lattice: All eight subsets of U, L, F are enumerated. "A subset is observed sufficient when all primary worst-case ASRs are zero on isolated-eligible questions. It is observed inclusion-minimal when no immediate proper subset is sufficient... the full 2 cubed lattice is enumerated, so this checks every proper subset rather than assuming monotonicity."

Three deterministic exact visible detectors are studied:

• U(τ) = nonempty final with no search

• L(τ) = ∃c ∈ C(τ) ∩ P: c ∉ E(τ) (a corpus-valid citation absent from retrieved passages)

• F(τ) = ∃c ∈ C(τ): c ∉ P (nonexistent citation ID)

For S ⊆ U, L, F: R S(τ, x) = R 0(τ, x) − Σ λ j j(τ), with manifest-fixed λ U = 1.6, λ L = 1.2, λ F = 1.0. The base reward is R 0 = 1.15a + 1.05g + 0.30c − 0.04t − 0.80v − 0.55h − 0.004l, where "the generic rate averages seven Boolean flags, including under-retrieval, cited-not-retrieved, fake citation, support-ID mismatch, and repeated query. Because L is one of them, an isolated L flip already contributes −0.55/7 ≈ −0.0786 inside R0; R[L] strengthens an existing detector rather than introducing one. R full additionally includes answer-without-citation, repeated-query, over-retrieval, and oracle support-ID penalties (the latter reads benchmark annotations and is never called candidate-visible").

Operators include:

• Same-final deletion: preserves final bytes, removes search

• Laundering: answer/search fixed, replaces citation with a real but unretrieved ID

• Fake ID: replaces citation with nonexistent corpus ID

• Gold stress and support-ID (oracle-only) interventions

The primary generator "builds up to eight candidates by lexical overlap with the visible question and candidate answer. A separate BM25 generator uses the same visible fields and evaluates budgets K ∈ 1, 2, 4, 8, 16. Neither receives an example record, gold answer, support ID, EM label, or evaluation field."

• Main pools: Four Qwen3-8B best-of-eight pools: 200 questions each from HotpotQA and 2WikiMultiHopQA, and 200 MuSiQue questions each at retrieval cutoffs five and eight. The MuSiQue pools repeat question IDs, so 800 rows represent 600 unique questions. Exactly 593 question clusters are isolated-eligible for all three primary attacks.

• Cross-model replication: 1,000 logged HotpotQA trajectories each for Qwen3-1.7B, Qwen3-8B, Qwen3-14B, and Meta-Llama-3-8B; per-model sample sizes 904–995 after isolation filtering (3,829 isolated trajectories total).

• Matched policy audit: Eight-GPU Search-GRPO runs with group size eight, strict 5,000,000 global generated-action-token budget. "Batch-matched R0 and R[L] both complete at update 912 with 5,003,240 and 5,003,684 tokens... only the reward configuration adds −λL L. All 192 update-0 non-reward records match exactly. Each arm stores 58,368 training trajectories. Tail evaluation uses 256 nontraining questions per benchmark, one greedy and four fixed-seed samples per question, giving 11,520 trajectories total. The pre-specified EM non-inferiority gate requires the paired lower confidence bound to exceed −2 points on each benchmark."

1. Exact controls falsify two broad loopholes. "Outcome-only rewards give ASR 1 for same-final, laundering, fake-ID, repeated-query, and oracle unsupported-citation attacks. Adding tool cost still gives ASR 1 for all except repeated query; search deletion is positively rewarded because it saves cost. In contrast, R0 has zero same-final and fake-ID ASR on 593 isolated questions. The exact upper bound is 0.50%. For same-final deletion, the implemented generic penalty already exceeds the saved cost."

2. Adaptive laundering exposes the actual gap. "Citation laundering leaves answer and search fixed but substitutes a real corpus ID absent from prior observations. Under R0, the First-visible candidate succeeds 4.30% and the Oracle-worst candidate succeeds 6.66%. The corresponding average worst-case margin is −0.489. R[L] reduces both First-visible and Oracle-worst ASR to zero, with mean worst-case margin −1.689. Notably, Rfull is stronger on average yet retains 3.37% Oracle-worst ASR: replacing a citation can remove its active oracle support-ID penalty and partially cancel the new membership penalty."

The gap is robust to pool selection: Under stored, first, hash-random, all-eight, R0-best, and gold-informed pool selection, First-visible R0 isolated laundering ASR stays between 3.96% and 4.68%; Oracle-worst ASR stays between 7.08% and 7.81%. The BM25 attack yields 4.38% offline ASR at K=1, reaching 13.74% at K=16 for oracle-worst.

3. One strengthening is observed inclusion-minimal. "R0, R[U], R[F], and R[U+F] all retain the same 6.7% Oracle-worst laundering failure. Every subset containing L has zero observed primary ASR. Consequently R[L], not the old three-check bundle, is the observed inclusion-minimal contract for these attacks in the context of R0. Weight sensitivity: At scale zero, laundering ASR is 6.7%; at scales 0.25 and 0.5 it is 4.0% and 3.2%; the canonical scale one reaches zero and shifts mean margin from −0.489 to −1.689."

4. Cancellation explains why broader hardening is weaker. The paper formalizes cancellation credit: for expanding S to T ⊇ S, C T(A, τ) = −Σ j∈T λ j d j(A, τ), with the expanded margin M T = M S + C T. A pair rejected by S re-enters the attack set under T exactly when C T(A, τ) ≥ −M S(A, τ). In the saved case, d support = −1, hence C = 0.8 and the R[L] margin −0.38625 becomes +0.41375 under Rfull. Among originals with an active support-ID penalty, Rfull First-visible and Oracle-worst ASR are 6.33% and 13.92%; without it they are 0.00% and 0.22%. Every successful active-stratum pair removes the 0.8 penalty. R[L] strictly rejects all attacks in a finite candidate set because λ L = 1.2 exceeds the audited maximum R0 gain of 0.81375.

5. Cross-model transfer. "Every model exhibits positive R0 adaptive-laundering ASR... Oracle-worst ASR ranges from 10.57% to 19.60%; the question-weighted aggregate is 13.69% over 3829 isolated trajectories. R[L] has zero observed success for all four models, with per-model upper bounds of 0.30–0.33%. The strict full reward retains 4.70–8.44% worst-case ASR."

Offline utility: On saved best-of-eight pools, R[L] and R[U+L+F] select exactly the same aggregate EM, citation precision, support recall, valid-final rate, and search cost as R0.

Evidence quality improves under matched compute. "On 256 greedy questions per suite, equal-suite EM changes by +1.43 points ([−0.39, 3.26]), while the −2 point EM non-inferiority gate passes on HotpotQA and 2Wiki but not MuSiQue. Citation precision and support recall improve by +2.02 ([0.46, 3.56]) and +1.46 ([0.33, 2.64]), while unsupported citations fall by 1.69 points (95% CI for R[L]−R0: [−3.39, −0.13])." Four-sample evaluation corroborates this, with precision improving by +1.72 ([0.50, 2.93]), recall by +1.73 ([0.90, 2.56]), while EM and F1 intervals cross zero.

Targeted attackability improves on two suites. "For the First-visible laundering edit, attackability under the fixed base scorer R0 falls by 2.73 points on 2Wiki (95% CI for R[L] − R0: [−5.08, −0.39]) and 2.34 on MuSiQue ([−4.69, −0.39]). The HotpotQA difference is −0.39 ([−1.56, 0.78])."

Detector signal is sparse. R[L] sees 18 strict-L rows among 58,368 trajectories (0.03084%), spanning seven groups; five change normalized advantages and two are exactly canceled. In expanded evaluation, R0 emits no strict-L event among 768 greedy or 3,072 sampled trajectories; R[L] emits one and six. The implementation therefore transmits a sparse signal, but natural L is not reduced.

The paper explains why group normalization can erase the detector: "For binary li, the squared magnitude of its centered contribution is (1/K)Σ(e'r i − e i)2 = λ2 L l̄ g(1 − l̄ g). If every rollout in the group has the same detector value, this quantity is zero: subtracting the group mean removes the penalty exactly... A mixed group is therefore necessary, though not sufficient, for L to change normalized advantages."

The paper's implications: "Audit the smallest visible contract. Full enumeration shows that only targeted L strengthening adds observed robustness beyond R0... Separate score preference from behavior incidence. Counterfactual ASR tests scorer preference on saved pairs; natural incidence requires fresh rollouts and enough events... Use margins and upper bounds. ASR hides severity and vulnerable tails. Report paired margins and an exact upper bound with n."

Limitations acknowledged: the audit tests structured citation IDs and local retrieval; free-form citations, semantic paraphrases, live-web state, and corpus poisoning need other operators. Dense retrieval and visible-only LLM attacks remain untested. Zero-ASR, minimality, and finite-set margins are conditional on the pools, eligibility rules, generators, and closed corpus. Proof of retrieval is not proof of semantic support. The strict policy comparison uses one matched run per arm; paired intervals measure question uncertainty, not between-run variability, and seven natural R[L] events provide too little power for small rare-event changes.

The conclusion states: "HERALD makes proof-of-retrieval rewards falsifiable through paired audits. Exact controls isolate citation laundering and identify targeted L strengthening as the observed inclusion-minimal repair; cancellation explains why broader oracle hardening can be weaker. Pool sensitivity, BM25 and nonlexical candidates, and four-model replication support the scoring result. Matched-token R[L] training improves aggregate evidence quality and targeted attackability on two benchmarks, but not natural L incidence or uniform accuracy non-inferiority. Reward audits should separate scorer robustness, training exposure, and policy transfer."

Based on HERALD, an improved AI system for search-agent reinforcement learning should include the following capabilities.

1. Reward-as-program unit testing with paired counterfactual audits.

The system should treat every reward function as code under test and automatically generate paired interventions on the same question—not just global attacks—so it can isolate whether a score change is caused by retrieval, citation, or answer edits. It must record exactly which fields each operator can access and forbid oracle-gold fields from being visible to candidate generators.

2. Attack eligibility and detector isolation by default.

Instead of reporting crude attack-success rates on arbitrary edits, the system should only count an attack as successful when:

• The target detector was false on the original trajectory and true on the edited trajectory.

• All unrelated visible flags remain unchanged.

• The question is eligible for that attack (an already-invalid original is not counted).

This prevents inflated zero-attack claims and false confidence.

3. Complete detector-lattice enumeration for minimal repairs.

The system should enumerate all subsets of candidate detectors (e.g., U, L, F) rather than testing only a bundled detector. It should report which subset is observed sufficient and observed inclusion-minimal. This allows the system to discover that a single targeted penalty (e.g., “citation not retrieved”) is the minimal contract, and that a broader bundle with oracle support-ID penalties can be weaker due to penalty cancellation.

4. Paired margins plus exact upper bounds, not just attack-success rates.

For every intervention, the system should report:

• Paired reward margin R(edited) − R(original).

• Attack-success rate including ties.

• For zero-event results, an exact one-sided 95% upper bound 1 − 0.05(1/n) instead of a degenerate interval.

This separates severity from frequency and avoids overstating certainty on small samples.

5. Penalty-cancellation analysis across reward expansions.

The system should compute cancellation credit C T = −Σ λ j d j when moving from one detector set to a superset. It should flag cases where expanding a reward with an oracle penalty (like support-ID mismatch) re-admits attacks because fixing the citation removes a larger penalty than the new penalty adds. This explains why “more penalties” can be weaker and lets the system choose the minimal robust reward.

6. Cross-model and pool-robust auditing before policy training.

The system should validate candidate rewards across:

• Multiple pool-selection strategies (stored, first, hash-random, all-eight, R0-best, gold-informed).

• Multiple generators (lexical overlap and BM25 with varied budgets).

• Multiple base models (e.g., 1.7B, 8B, 14B, and a different architecture).

This makes robustness claims transferable rather than overfit to one logging policy.

7. Matched-compute policy transfer tests with non-inferiority gates.

When moving from an audited reward to actual policy optimization, the system should:

• Use exactly matched training compute (global action-token budget, same group size, same update schedule).

• Verify that non-reward records are identical at initialization.

• Pre-specify an EM non-inferiority gate and report evidence-quality metrics (citation precision, support recall, unsupported-citation rate) alongside attackability.

• Separately report natural detector incidence in fresh rollouts, accounting for group-normalization effects that can erase sparse detector signals.

8. Sparse-signal diagnostics for group-normalized advantages.

The system should compute, for each binary detector, the squared magnitude of its centered contribution λ2 l̄ g(1 − l̄ g). If a detector is constant within a group, the system should warn that the penalty is exactly subtracted out and cannot change normalized advantages. This tells engineers whether a reward fix is truly inactive in policy learning or simply diluted by batch composition.

• Find reward loopholes before costly policy optimization, while rejecting false positives and false negatives from unisolated, ineligible attacks.

• Identify the smallest sufficient reward repair—for example, adding only the “citation-not-retrieved” detector, not a large bundle—and prove why the larger bundle underperforms.

• Quantify attack vulnerability with confidence, reporting worst-case paired margins and exact upper bounds so stakeholders know both the rate and severity of remaining failures.

• Prevent penalty-cancellation failures by detecting when oracle support-ID penalties cancel newly added citation-membership penalties.

• Produce transferable audit conclusions across models, pools, and retrieval budgets, instead of conclusions tied to one logging policy.

• Evaluate policy-side effects honestly: improved evidence quality and reduced targeted attackability on some benchmarks, without claiming uniform accuracy gains or natural-incidence reductions.

• Explain why a reward fix appears inactive during training—separating “no signal in natural rollouts” from “group normalization erased the signal”—and guide the design of mixed-group batches or alternative normalization when sparse detector signals matter.