Retrieval & Search / COLM Workshop 2026 (Agent Behavior)

A Search Agent Can Get the Right Answer Before It Has Earned It

The Epistemic Ledger tracks which conditions a search agent has supported. The COLM workshop results show what changes when the agent sees that state during its search.

When Is Enough Not Enough? Illusory Completion in Search Agents

Dayoon Ko, Jihyuk Kim, Haeju Park, Sohyeon Kim, Dahyun Lee, Gunhee Kim, Moontae Lee, Kyungjae Lee

Overview

Ask an agent for someone who meets three conditions and it may verify two, assume the third, and confidently return a name. The name can even turn out to be right. This study calls that premature sense of completion illusory completion. It tests whether making the status of each condition visible improves how agents search and decide when to stop.

Key Findings

Diagnose the gap between evidence and belief

Given a question with several independent conditions, an agent can find a plausible candidate and stop before it has checked everything. The workshop evaluation selects 484 questions from six benchmarks, using reasoning graphs of depth one and width at least three. This isolates the work of checking independent constraints. Results on this set do not cover all forms of multi-hop search, especially chains in which one answer is needed to formulate the next question.

The Epistemic Ledger records what the retrieved evidence establishes, Et(k,Ci)E_t(k,C_i), and what the agent says it believes, Bt(k,Ci)B_t(k,C_i), for candidate kk and constraint CiC_i at step tt. It also records which candidate the agent is actively pursuing. The paper marks a committed final candidate aTa_T as underverified if any condition lacks positive support.

U(aT)=1 ⁣[status⁡(aT)=ACTIVE ∧ ∃Ci∈C: ET(aT,Ci)≠SATISFIED].U(a_T)= \mathbf 1\!\left[ \operatorname{status}(a_T)=\mathrm{ACTIVE} \ \land\ \exists C_i\in\mathcal C:\, E_T(a_T,C_i)\ne\mathrm{SATISFIED} \right].

This distinction lets the ledger separate four process failures. The diagnoses can overlap within a single run, so the four rates should not be added as if they partitioned the questions.

DiagnosisEvidence and belief at the failure
Bare assertionThe agent affirms a condition that the evidence leaves unknown
Overlooked refutationRetrieved evidence contradicts a condition, while the agent fails to deny it
StagnationEvidence and belief stop changing for an active candidate with an unknown condition. The paper uses a window of three steps
Premature exitThe agent stops while its candidate still has at least one condition without positive support
In the paper's music-search example, the agent commits to Drake. Its ledger still records unsupported and contradicted requirements.
In the paper's music-search example, the agent commits to Drake. Its ledger still records unsupported and contradicted requirements.

Score verification separately from correctness

A candidate may meet every condition in the world even if the agent never obtained the evidence. Conversely, when the evidence supports a candidate but the final answer is wrong, the evaluation still counts it as wrong. The two rates in the workshop manuscript use the same denominator of evaluated questions, NN.

Acc=1N∑j=1N1[answer j is correct],UAR=1N∑j=1NU(aT,j).\mathrm{Acc}=\frac{1}{N}\sum_{j=1}^{N}\mathbf 1[\text{answer }j\text{ is correct}], \qquad \mathrm{UAR}=\frac{1}{N}\sum_{j=1}^{N}U(a_{T,j}).

The share of correct answers that are underverified has a different denominator. For WebExplorer, the figure reports about 11% of all questions as correct but underverified and 14% as correct and verified. With the rounded bars, that means roughly 11/(11+14)=44%11/(11+14)=44\% of its correct answers remain underverified. A high rate on this conditional measure can be hidden when a benchmark checks only the answer.

Figure 2 divides outcomes into four groups using correctness and verification. The blue hatched part shows correct answers that remain underverified.
Figure 2 divides outcomes into four groups using correctness and verification. The blue hatched part shows correct answers that remain underverified.

The ledger itself is model-judged. The paper audits 100 selected examples with three human annotators per example and reports 91% agreement for the majority vote, with Fleiss' κ=0.76\kappa=0.76. This checks the annotation method on those samples. It does not establish that every retrieved passage was interpreted correctly, or that the evidence available online was complete.

Put the evidence state into the next decision

The offline Epistemic Ledger reads both retrieved observations and the agent's beliefs. Live Ledger is an inference-time intervention. It updates the evidence state after a retrieval step and shows the new ledger to the agent before it reasons or acts again. It does not record a belief for the not-yet-generated next trace.

Lt+1=Update⁡ϕ(Lt,ot),(τt+1,at+1)∼π( ⋅∣Ht,Lt+1).L_{t+1}=\operatorname{Update}_{\phi}(L_t,o_t), \qquad (\tau_{t+1},a_{t+1})\sim\pi(\,\cdot\mid H_t,L_{t+1}).

The tracker is a 4B Qwen3.5 model trained on decompositions and stepwise updates from gpt-oss-120b. The authors generate demonstrations on MultiConIR and HDS-QA, retain runs with correct final answers, and fine-tune on their ledger updates. The intervention targets what the policy sees between steps. The policy still chooses queries, evidence, and its stopping point.

Agent in workshop Table 1Accuracy beforeAccuracy with ledgerUAR beforeUAR with ledger
Tongyi DeepResearch 30B26.9%39.6%64.9%58.4%
ReAct 20B22.3%30.3%67.8%64.0%
ReAct 120B20.1%33.1%76.6%65.5%

These are means across three runs. All three pairings improve both metrics, including +13.0 accuracy points and −11.1 UAR points for ReAct 120B. UAR still exceeds 58% for every ledger-augmented agent in these rows. The added state improves checks without making completion reliable on its own.

Check which failures move and which persist

Figure 3 shows that the same intervention changes different agents in different ways. Premature exit falls by 20.4 points for Tongyi DeepResearch and 18.5 for ReAct 120B. Overlooked refutation falls by 13.2 for ReAct 120B and only 0.9 for Tongyi DeepResearch. Bare assertions increase in the three reported pairings. One plausible reading is that some agents now address a previously skipped condition but still accept it without evidence. That is why a shorter list of unresolved conditions is insufficient as a stopping signal.

The workshop's failure-pattern comparison shows large reductions in premature exit and smaller changes in some other errors, including increases in bare assertions.
The workshop's failure-pattern comparison shows large reductions in premature exit and smaller changes in some other errors, including increases in bare assertions.

The 7B process-feedback control in Table 2 uses the same Qwen2.5-7B-Instruct backbone. Live Ledger improves both headline metrics relative to ReAct and the single-pass comparison methods. Three judgments per step, combined by turn-level majority vote, help Live Ledger more than ReSeek on this setup. The common backbone makes the systems more comparable, although the added judgments still cost compute and the methods differ in how they produce feedback.

7B process-feedback conditionAccuracyUAR
ReAct, single pass16.6%82.5%
HiPRAG, single pass18.1%81.4%
ReSeek, single pass13.3%82.5%
ReAct + Live Ledger, single pass21.0%78.2%
ReSeek, three judgments14.1%83.8%
ReAct + Live Ledger, three judgments27.7%75.7%

Keep the workshop and arXiv comparisons separate

The later arXiv revision reports a different set of agents and experimental comparisons. Its six main accuracy gains range from 4.4 to 16.1 points, including DeepSeek-V4 moving from 43.6% to 59.7%. Those values belong to the revised preprint. The tables and figures above report the supplied COLM Workshop on Agent Behavior version.

Questions & Answers

Q: Why can a correct answer be underverified?

A: The candidate may satisfy a condition in reality even when the agent never retrieved evidence of it. The ledger evaluates what the agent established during the run as well as whether the final answer matches the reference.

Q: Does Live Ledger take over the search?

A: The tracker surfaces condition states. The agent still decides what to search, what evidence to use, and when to answer.

Q: Can the ledger make mistakes?

A: The states are inferred from retrieved evidence, and a mistaken update can send the agent toward the wrong candidate or an early exit. Evidence quality, retrieval coverage, and the tracker’s judgments each affect the result.

Future Ideas

Attach an evidence receipt to a literature-search result

Ask a research assistant to attach a source passage to each requested criterion, such as population, study design, and outcome. Keep unchecked conditions visible and preserve contradictory passages when available. Compare a live ledger with a checklist prompt and ordinary agent search at the same call budget.

Use a benchmark where experts can independently verify each reference and some requests have no known match. Measure final-answer accuracy, evidence support, abstention, and the time a reviewer takes to check the answer.

Sources

Original abstract

Recent search agents interleave multi-turn reasoning with tool calls to achieve strong performance on multi-hop and long-horizon benchmarks. Yet it remains unclear whether they reliably reason and verify across all of a question’s requirements. We study this in the multi-constraint setting, where a valid answer must satisfy several constraints simultaneously. Here, agents frequently exhibit illusory completion: they believe a task is complete despite unresolved or violated constraints, producing underverified answers. To diagnose this behavior, we introduce the Epistemic Ledger, an evalu-ation framework that tracks evidence retrieved and the agent’s stated belief for each constraint across turns. This reveals four recurring failure pat-terns: bare assertions, overlooked refutations, stagnation, and premature exit. Building on this diagnosis, we propose Live Ledger, a lightweight 4B-parameter tracker that surfaces constraint states to the agent at inference time. It improves the accuracy of a 30B-trained policy by 12.7%p and of a 120B-prompted agent by 13%p, while reducing underverified answers by 6.5%p and 11.1%p, respectively.