acceptodds
Under review as a conference paper at ICLR 2027

When Agents Choose What to Observe: BEATS – Answer-Free Test-Time Selection for Verifiable-Reward Agents

Abstract

Verifiable-reward methods typically evaluate an output against a fixed problem instance or an externally supplied evidence record. In partially observable agent environments, however, the policy may also control which information is acquired. Verification is therefore conditional on a policy-constructed record: a certificate can be valid relative to that record while its decision is wrong under the complete record. We study this failure surface in LegalEvidenceGym, a synthetic executable testbed that separates latent facts, available sources, the agent's acquired information state, record-entailed decisions, and structured certificates. Across six registered cost-penalized RL runs, optimized reward, certificate validity, and joint decision–certificate success increase, while decisive-evidence recall (DER) and joint correctness on controlled Evidence-Twin pairs (ETC) decrease. We call this longitudinal signature Evidence Collapse; it is consistent with shortcut learning under the optimized objective but does not identify a unique cause or a verifier error. We introduce Best-of-N Evidence-Aware Trajectory Search (BEATS), an answer-free, training-free test-time procedure. BEATS diversifies candidate information states with bounded public prefixes, ranks them using only replayable public features, and serializes a certificate entailed by the selected record. On 150 held-out episodes (75 Evidence-Twin pairs) evaluated under six frozen Qwen checkpoint conditions, BEATS@4 achieves 92.33% joint success, compared with 86.89% for the strongest same-pool, same-recovery baseline, deepest-prefix Max-Probe@4 (+5.44 points; pair-clustered 95% CI [2.44, 9.00]), while reducing mean environment investigation cost by 23.3%. These results show that terminal verification should account for how an agent constructs its information state, not only whether its final output is internally valid.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Large‑language‑model agents, Verifiable reward reinforcement learning, Evidence collapse

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_pr4MOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a verification gap in partially observable agent settings. When the policy chooses which evidence to acquire, a verifier that checks a structured certificate against the acquired ledger certifies record-relative validity, not complete-record correctness (Eq. 2). To study this, the authors build LegalEvidenceGym. It is a synthetic environment with five stylized employment-termination rule programs, 1,500 deterministic episodes, and an exact public engine ΦR\Phi_R that maps a ledger to element states. It also includes Evidence-Twin pairs that differ in one source condition.

The paper makes three empirical contributions. First, a static GPT-4o experiment shows a decision–certificate gap (92.8% DA vs. 84.2% PVS). Second, the paper names a pattern “Evidence Collapse”: across 3 seeds × 2 cost-penalized GRPO objectives on Qwen2.5-7B, reward, CV, and PVS rise while DER, ETC, and DA fall. Third, BEATS is a test-time procedure that works as follows:

It generates N=4 trajectories with forced public probe prefixes of depth 0–3. It replays each one without answers. It ranks them with a lexicographic key over recoverability, error counts, evidence completion pevp_{\text{ev}}, and cost. It canonically re-serializes the certificate from the selected ledger.

On 150 held-out episodes × 6 checkpoints, BEATS@4 reaches 92.3% PVS, versus 86.9% for deepest-prefix Max-Probe@4 with identical recovery (+5.44, pair-clustered CI [2.44, 9.00]). It does so at 23.3% lower environment cost, close to an evaluator-only pool oracle (93.0%).

Critical strengths

S1. The conceptual boundary is stated precisely and operationalized well. Eq. 2 cleanly separates record-relative validity from complete-record correctness. The environment exposes each layer (latent world, available sources, acquired ledger, entailed decision, certificate) as a separately measurable object. Evidence-Twins combined with the joint ETC metric extend contrast sets from output sensitivity to acquisition behavior, and they refuse credit for repeating one label across a pair. This is the most reusable artifact in the paper. It gives anyone training tool-using agents against terminal verifiers a controlled test of whether decisions track decision-relevant evidence.

S2. Experimental hygiene and claim calibration are well above typical. The paper does several things right:

The selector is frozen on validation before test. All selectors draw from the same candidate pool and get identical recovery. Bootstrap resampling is clustered by twin pair, so 900 correlated observations are not treated as independent. An evaluator-only oracle measures headroom. Per-seed results are reported. The authors explicitly decline to claim reward hacking.

This makes the numbers trustworthy. It also makes it possible to run the decompositions below from the reported tables, which is to the authors’ credit even where those decompositions cut against the framing.

Critical weaknesses

W1. “Evidence Collapse” is the optimum of the stated objective, and the control that could make it more than that is missing.

Table 1 decomposes the reward gain almost exactly. With Routcome=1[d^=d⋆]−0.05c−pinvalidR_{\text{outcome}} = \mathbf{1}[\hat d = d^\star] - 0.05c - p_{\text{invalid}}:

The cost reduction (Δc=−5.50\Delta c = -5.50) is worth +0.275+0.275. Decision accuracy, the only correctness term, falls by 0.0780.078. The net is ≈+0.20\approx +0.20, consistent with the rise in Fig. 3A.

For Certificate-GRPO, 0.05×5.15+0.218 (ΔCV)−0.113 (ΔDA)≈+0.360.05 \times 5.15 + 0.218\,(\Delta\mathrm{CV}) - 0.113\,(\Delta\mathrm{DA}) \approx +0.36, consistent with Fig. 3C. GRPO is doing what the reward pays for. At λ=0.05\lambda = 0.05, five units of cost are worth more than eight points of decision accuracy, so investigating less is optimal, and lower DER and ETC follow directly. An expert shown the reward function would predict this outcome.

The paper’s thesis is stronger: terminal reward and record-relative verification do not, by themselves, reward adequate investigation. But at λ=0\lambda = 0 the outcome term does reward acquiring decisive evidence, since on twin pairs that is the only way to be right on both. The thesis and the cost-tradeoff account therefore make different predictions. The zero-cost or fixed-cost control that the authors acknowledge is missing (Sec. 4.3) is exactly the experiment that separates them. For Certificate-GRPO in particular, if the validity bonus alone drives smaller ledgers at λ=0\lambda = 0, that would be genuine support for the thesis. Without this control, or a λ\lambda sweep, the second contribution is a name for the behavior the reward specifies.

The cross-checkpoint Spearman correlations do not close this gap. Reward and DER both trend monotonically with update number, so their rank correlation largely reflects the shared time trend.

W2. BEATS’s gain over the strongest baseline is a validity gain, not an evidence-sufficiency gain, and the method relies on an exact public engine that the named application domains lack.

The +49 PVS gain is smaller than the +55 gain in valid outputs. Conditional on a valid certificate, decision accuracy is 95.3% for BEATS versus 95.7% for Max-Probe, and Max-Probe also has higher DER (0.942 vs. 0.885). So the ledgers BEATS selects are not more decision-sufficient. BEATS avoids more trajectories that end invalid.

Canonical serialization yields a valid certificate for any ledger. The residual invalid outputs must therefore come from non-recoverable trajectories (budget, horizon, action, or parse failures). Deep prefixes make these more likely under the 12-unit evaluation budget. As this account predicts, the gap is largest in the high-cost stratum (0.773 vs. 0.640). The leading terms of K(r)K(r) (vrecv_{\text{rec}} and the error counts) capture this without pevp_{\text{ev}} or cost. On the evidence shown, the PVS gain does not support the framing that the relevant selection object is the information state. The deciding criterion is terminal recoverability.

Separately, the pipeline leans on ΦR\Phi_R throughout:

Recovery submits fR(ΦR(L))f_R(\Phi_R(L)). pevp_{\text{ev}} is read off the engine. A single sample with recovery already reaches 0.784 PVS, versus 0.418 for greedy decoding without it.

“Answer-free” is accurate, but it says little when the decision function is public and exact. In medical diagnosis, auditing, or web search, which the conclusion names, estimating element resolution without such an engine is the hard problem (cf. SeekBench, S2G-RAG), and BEATS assumes it away.

Finally, the 23.3% cost reduction is measured against the selector that, by construction, picks the most expensive prefix. Self-Consistency (5.20) and Certificate-only (4.92) are both cheaper than BEATS (5.42), and N=4 uses about 2× the model tokens of greedy decoding.

Questions for authors

Q1 (could change my assessment). Please report a “deepest recoverable prefix” baseline. It would filter candidates by the first four terms of KK (vrecv_{\text{rec}} and the three error counts), then take the deepest remaining prefix. Please also report a leave-one-term-out ablation of KK. If this baseline reaches ≈0.92 PVS, then pevp_{\text{ev}} and cost contribute savings but not correctness, and the contribution should be reframed accordingly.

Q2 (clarification). Please break down the invalid outputs (≈83 for Max-Probe, 28 for BEATS) by cause: budget exhaustion, horizon, invalid action, or parse error. Please also report BEATS vs. Max-Probe at 20- and 30-unit evaluation budgets. Does the gap survive when the budget no longer truncates deep prefixes?

Q3 (could change my assessment). Please evaluate a scripted, non-LLM acquisition baseline. It would acquire public sources in cost order until ΦR\Phi_R resolves every element or fixes the burden-based decision, then submit the canonical certificate. What PVS and cost does it reach? Recovery already computes the decision from the ledger, so this isolates what the LLM contributes.

Q4 (could change my assessment). Please run one λ=0\lambda = 0 (or fixed-cost) GRPO run per objective, even single-seed, and ideally a small λ\lambda sweep. Does DER still decline? If it does, Evidence Collapse is a finding about terminal verification. If it does not, it is a cost tradeoff and is better presented as a DER-vs-λ\lambda curve.

Q5 (clarification). Outcome-GRPO does not reward validity, yet CV rises by 0.28. Is this mechanical? Smaller ledgers leave more elements UNRESOLVED and create fewer opportunities to overclaim. If so, CV↑ and DER↓ are one effect rather than two co-moving signals. Please report CV conditioned on ledger size.

Q6 (clarification). How many key orderings and N values were tried on validation before the freeze? Please also report DA for every row of Table 2.

Suggestions (do not affect my score):

The strongest version of this paper would lead with the environment and twin diagnostic, and turn the cost tradeoff into a predictive DER-vs-λ\lambda law. Sec. 4.2 is a weak fit. It uses a single unrecorded GPT-4o snapshot, and it tests a different failure mode (overclaiming on a fixed record, not record construction). Consider moving it to the appendix. The Gemma replication belongs in the main text. The final paragraph of the conclusion prescribes training-time fixes that the paper does not test.

Reviewer_WJ6kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies agents that gather evidence before making decisions. While a verifier can check whether the final certificate is consistent with the collected evidence, it cannot tell whether the agent missed important evidence that could have changed its decision. To investigate this, the authors introduce LegalEvidenceGym, a synthetic benchmark based on employment-termination rules, with paired episodes that differ in only one piece of evidence. Their experiments show that cost-penalized RL improves reward and certificate validity but leads agents to collect less decisive evidence, making them less reliable on these paired episodes. The authors call this Evidence Collapse. To address this, they propose BEATS, a training-free method that explores multiple trajectories with different starting probes, replays them, and selects the best one using publicly available features. BEATS outperforms the strongest baseline on held-out episodes while also reducing investigation costs.

Critical strengths
  • The paper highlights a key problem: an agent may produce a valid certificate based on the evidence it collected, even if it missed evidence that could have changed its decision.

  • The experiments are fairly well controlled. The methods use the same candidate pool and recovery step, and the authors fix their procedure on validation data before testing. The paper is also reasonably careful about the claims it makes.

Critical weaknesses
  • Diagram seems fully claude generated. Given reviewers are expected to give substantial time to review such papers, it is really inappropriate to have AI generated main architectural diagrams.

  • Since the RL objective penalizes investigation costs, agents collecting less evidence is not surprising. The paper does not include a zero-cost or fixed-cost control (Section 4.3), so it is hard to tell whether Evidence Collapse is a separate problem or simply a consequence of the training objective.

  • The gains from BEATS may depend on the synthetic setup. The method uses an exact rule engine to estimate evidence completion and recover certificates. The results also suggest that recovery accounts for much of the improvement: BEATS without recovery scores 0.583, while Max-Probe with recovery reaches 0.869. It is unclear whether BEATS would work as well on real tasks where such a rule engine is unavailable.

Questions for authors
  • What happens if GRPO is trained without a cost penalty, or under a fixed investigation budget? This would help establish whether Evidence Collapse is caused by cost penalization.

  • Can BEATS work with an estimated evidence-completion score from an LLM instead of an exact rule engine?

  • Do the results change if the order of the selection criteria is changed? How was this order decided?

  • In Table 1, decision accuracy drops after RL even though PVS improves. Does the higher PVS reflect better decisions or mainly better certificates?

  • Figure 1 is difficult to read because the text is too small. Could the figure be simplified?

Reviewer_789VOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper looks at the verification problem from a perspective of partial observability, where the information and trajectories are determined by the policy and therefore may limit the judge in terms of what it has access to in order to properly verify. The authors propose a new synthetic environment, LegalEvidenceGym, analyze this issue, and propose a Best-of-N trajectory search to ameliorate it.

Critical strengths
  • The underlying premise is interesting, albeit studied in a number of related work across other domains.
Critical weaknesses
  • There are a number of works in multi-modal verification that obtain additional evidence for verification via a number of mechanisms. See [A] for just one example of a method and AJ-Bench [B] as a benchmark. This paper is not well-situated with respect to the state of art and related work. Further, instead of creating a new unknown benchmark environment

  • The paper introduces an unknown new environment with basically no details about the environment in the main paper (it's all in the supplementary). The environment is extremely simple consisting of five synthetic employee termination rule templates, and a small number of episodes. There is no justification given for why this is a realistic scenario that might be useful in the real world. Given that, it is impossible to tell what the intricacies and potential issues/biases of the environment. If papers introduce new environments and use it as the sole domain for experiments, it must provide thorough details and comprehensive benchmarks with the current state of art.

  • The method is an extremely simple one that uses best-of-N selection, which is a well-known technique. It's not clear what the scientific contribution of the paper is.

  • This paper is extremely difficult to read with dense language that requires re-reading most sentences to understand what is being said. There is very little staging, intuition, or transitions and new jargon is consistently thrown in (often multiple in one sentence) without any explanation of what it means. This weakness is throughout the entire paper and so would require a complete re-write.

[A] Li et al., OS-Themis: A Scalable Critic Framework for Generalist GUI Rewards, https://arxiv.org/abs/2603.19191 [B] Shi et al., AJ-Bench: Benchmarking Agent-as-a-Judge for Environment-Aware Evaluation, https://arxiv.org/abs/2604.18240?utm_source=chatgpt.com

Questions for authors
  • Why is this benchmark useful for studying this task, what is the justification for its setup and realism for real-world applications, and what domains are the findings applicable to?

  • What is the scientific contribution of this paper, given that sampling-based test-time compute strategies are well-known and it is not clear what the unique aspect of its application here is?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.