acceptodds
Under review as a conference paper at ICLR 2027

Do Claims, Evidence, and Actions Align? Evidence-Linked Consistency Checking in Multi-Agent Systems

Abstract

Evidence can appear in a multi-agent log without reaching the agent whose claim depends on it. A factually correct claim can therefore lack task-required support, even when no statements contradict one another. We formulate consistency as satisfaction of task-defined obligations relating evidence, claims, and actions. This definition accounts for which sources an agent may use and the context in which it acts. We introduce ECoCheck (Evidence-linked Consistency Checking), which combines graph-based retrieval, source-linked fact extraction, symbolic checking, and diagnostic feedback. We evaluate detection on perturbed traces and task outcomes in tool collaboration, coordination, and social simulation. Across 120 recorded perturbation outcomes, ECoCheck records 38 detections versus 18 for a transcript-order comparator, Linear, with the largest difference on unsupported claims (17/30 versus 6/30). Under the full treatment, macro-average overall goal success in tool collaboration is 20.00 percentage points above the baseline without verification feedback, and coordination utility is higher in all nine task–scale cells. These comparisons assess checking and feedback together and do not isolate the effect of checking. The selected evidence, encoded requirements, and diagnostics show what each check is based on.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-Agent Systems, Consistency Checking

Reviews

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

The paper considers a problem in multi-agent systems: there may be a difference between the true state of a relevant variable (an item is refundable) and compliance with a task requirement that the state of the variable be reported to an agent that is to take action based on the variable (send a replacement item.) The paper proposes a method for checking that task completion requirements (transmitting state information to another agent who is required to have the information before acting). At least I think this is what the paper is about; it is so poorly written it is hard to tell.

Critical strengths
  • This might be an important problem, of how to ensure that information claims are properly shared between agents in a multi-agent setting.
Critical weaknesses
  • Terribly written and formulated with seemingly pointless formalisms and clearly AI written.
  • Experiments are never properly explained
  • No discussion of the real world importance of this problem of any explanation that is easy to understand of what the method is other than making checks other approaches (are they used?) don't make.
Questions for authors
  • What is the point of the paper? What is the motivation for why this is important or interesting to solve?
1 comment
AuthorsOpenReview ↗

Response to Reviewer A5Hp

Thank you for your valuable suggestions and questions.

1. What is the problem, and why does it matter?

A policy agent may know that an item is refundable while the coordinator has not received its report. The refund claim can be true, yet violate a task rule requiring receipt of the report before the claim. The introduction uses this example to explain why the required evidence must reach the agent making the claim (Section 1; Figure 1).

2. Why use the formalization?

Two traces can contain the same fact and final claim, but only one delivers the required report in time. A checker that sees only the fact and claim cannot distinguish them. Section 2.2 states the information requirement: the representation must preserve differences that change whether a task rule is satisfied. This motivates retaining report-delivery order and tool–result links.

3. How does the method work, and what do the experiments measure?

ECoCheck builds a typed graph of interaction records, retrieves relevant records, extracts facts with source references, and encodes selected task requirements for SMT checking. The resulting diagnostics guide feedback (Section 3; Figure 2). Table 1 describes how each environment uses that feedback.

The evaluation uses separate measures for checking and task performance:

  • Checker responses: ECoCheck records 38/120 flags versus 18/120 for Linear, which uses transcript-order retrieval and symbolic checking. On 30 clean controls labeled as satisfying the evaluated task obligations, false-positive rates are 1/30 (3.33%) and 3/30 (10.00%), respectively (Sections 4.2 and 5.1; Table 3).
  • Task completion: Scenario Benchmark judges user and system assertions; overall GSR requires both sets to be satisfied. Macro-average overall GSR is 56.67% for ECoCheck, 52.22% for Graph-LLM, and 41.11% for ordinary LLM refinement (Section 5.2; Table 4).
  • Coordination: On ten six-agent meeting-scheduling cases, ECoCheck's mean overlap penalty falls from 5.4 to zero, versus 4.0 at R3 under ordinary feedback. Mean total score rises from 25.7 to 32.1, compared with 26.4 at R3 under ordinary feedback (Section 5.3; Table 9; Appendix Figure 7).
  • Social simulation: Werewolf measures game outcomes under the combined private-role, voting-rule, and SMT treatment. Villagers win 1/10 Base games and 7/10 ECoCheck games in the outcome dataset (Section 5.4; Table 6).

4. Writing and presentation.

The introduction motivates the problem with the refund example. Sections 4–5 identify the feedback treatments, define the metrics, and explain what the results measure. The section structure, six original figures, and core formulation are retained. Appendix D places the Werewolf outcome and scheduling tables on the same pages as their respective plots. The AI-use disclosure remains as submitted.

Reviewer_fJmVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1(−1)
Soundness
1(−1)
Read review
Paper summary

The paper proposes ECoCheck, a consistency-checking framework for multi-agent collaboration. ECoCheck first constructs a typed interaction graph from interaction logs, performs Graph-CoT-style evidence retrieval over the graph, and extracts the retrieved records into source-linked FactIR. It then verifies whether task-defined obligations are satisfied by encoding them as SMT formulas and checking with a symbolic solver. The resulting diagnostics are then provided to the agents as feedback.

The main contribution is reformulating multi-agent consistency as the satisfaction of task-defined obligations instead of factual correctness or answer agreement. The authors implement this as a graph-based neuro-symbolic checker and show gains across three environments.

Critical strengths

The proposed task-defined obligations aim to capture claims that are true and uncontradicted but lack task-required support, which prior methods based on factual correctness and answer agreement may fail to detect.

Critical weaknesses

Limited evaluation. My main concern with the paper is the limited number of baselines included. The authors compared ECoCheck against only two simple baselines: Base, which receives no feedback, and Linear, which uses the same pipeline without the interaction graph. This leaves several of the paper’s central claims untested. The paper’s central motivation is that checks based on factual correctness or answer agreement could miss claims that are true and uncontradicted but lack task-required support. However, no such method (e.g., a FActScore-style fact checker or a self-consistency/debate-based check) is evaluated on the same perturbed traces. Including such a comparison would provide strong empirical support for this motivation and help clarify where ECoCheck’s advantage comes from. Additionally, the current comparisons did not include a baseline that provides feedback without symbolic checking. This makes it difficult to for readers to separate the effect of symbolic checking from that of general language feedback. A comparison with an LLM-only critic (i.e., one that provides feedback directly from the same trace and task rules) could help clarify this.

Novelty needs clarification. The overall design, which uses an LLM to translate trajectory content into symbolic form and then checks it with a solver, seems to follow a well-established neuro-symbolic paradigm. Specifically, FormalJudge (Zhou et al., 2026) also extracts facts from agent trajectories, checks them against task constraints with Z3, and feeds the results back to agents. The paper currently discusses its relation to these works only briefly (Sections 1 and 6). A clearer discussion and positioning would help readers understand the paper's contribution better.

Writing clarity. I feel that the writing is sometimes hard to follow and could be improved. The paper heavily relies on abstract noun phrases that are introduced without an intuitive explanation at first use. e.g., "obligation-relevant distinctions", "adapter-specific structural validation", "evidence-linked interface". Explaining the concepts in simpler terms could be beneficial.

Questions for authors
  1. The authors noted in the paper that the framework relies on an LLM for retrieving evidence and that each step can fail. Could the authors report the retrieval recall, i.e., how often the relevant records/evidence are actually retrieved? Similarly, Section 4.2 notes that results on clean traces are not available in the archived data. Could the authors run ECoCheck on clean traces and report the false positive rate?

  2. The paper’s core motivating example is a report that was never delivered to the claiming agent. In the report-removal perturbation (Figure 3), ECoCheck detects 5/30 cases, compared with 4/30 for Linear. Could the authors comment on the relatively low detection rate and the small gap between the two methods in this setting, given its close connection to the paper’s motivation?

  3. Could the authors clarify which LLM is used for retrieval, extraction, and SMT generation?

2 comments
AuthorsOpenReview ↗

Response to Reviewer fJmV

Thank you for the concrete suggestions on baselines and presentation.

1. Feedback without symbolic checking.

The comparison now includes ordinary LLM refinement (LLM-base) and critics that give feedback directly from records retrieved by Linear-LLM or Graph-LLM. Linear-SMT, the original Linear comparator, and ECoCheck use symbolic checks (Section 4.1).

TreatmentMacro-average overall GSR
Base36.67%
LLM-base41.11%
Linear-LLM43.33%
Linear-SMT45.55%
Graph-LLM52.22%
ECoCheck56.67%

ECoCheck is 15.55 percentage points above ordinary LLM refinement and 4.45 points above the graph-based LLM critic. With linear retrieval, the SMT–LLM difference is 2.22 points. These macro-average differences use values before display rounding (Section 5.2; Tables 4 and 7).

Table 8 reports travel refinement over R0–R3. On ten six-agent CoLLAB meeting-scheduling cases, ECoCheck reaches mean total score 32.1 and mean overlap penalty 0 at R3, compared with 26.4 and 4.0 under ordinary LLM feedback (Section 5.3; Table 9; Appendix Figure 7). These are comparisons of the reported configurations; information access and total generation budgets are not verified as matched.

2. Factual checking and self-consistency/debate baselines.

The reported experiments do not include FActScore-style factual checking or self-consistency/debate on the same perturbed traces. Section 6 discusses their conceptual relation to ECoCheck.

3. Contribution and relation to FormalJudge.

Section 6 discusses the shared neuro-symbolic approach: FormalJudge extracts atomic facts from task-relevant trajectory context and checks their logical composition with Dafny and Z3 before feedback. ECoCheck adds a typed interaction graph that retains event ownership, local order, tool–result links, and dispatch–report flow. Queries follow these relations to retrieve evidence, and extracted facts retain source references. This supports checks of whether a required report reached the agent making a claim and whether a completion claim has the required tool result (Sections 2.2, 3, and 6).

4. Terminology and clarity.

The introduction now explains “obligation-relevant distinctions” through whether a report reached its recipient before a claim. Section 2 defines an obligation as a task requirement and admissibility as whether an agent may use a source. Section 3.2 explains structural validation as checking references to existing records; Figure 2 shows how those records enter checking and feedback.

5. Retrieval recall and clean false positives.

The 30 clean controls are labeled as satisfying the evaluated task obligations. Each false-positive rate is the number of clean traces flagged by that method divided by 30: 1/30 (3.33%) for ECoCheck and 3/30 (10.00%) for Linear (Sections 4.2 and 5.1; Table 3). Both counts include the one jointly flagged trace. No retrieval-recall measurement is available.

6. Report removal: 5/30 versus 4/30.

ECoCheck records one more flag. Section 5.1 explains that checking a missing report requires an applicable delivery rule and adequate communication coverage.

7. Models for retrieval, extraction, and SMT generation.

The configuration notes identify GPT-4o through OpenRouter for all three stages (Section 4.2; Appendix B.1).

Thank you for the response. I appreciate the authors' response and the added LLM-critic baselines, but my main concerns remain unaddressed. The paper's central motivation is that checks based on factual correctness or answer agreement miss claims that lack task-required support. However, no such baseline is evaluated on the same perturbed traces, and retrieval recall is still not reported.

In fact, the core motivating case is still not addressed. The paper is motivated by "a report that never reaches the claiming agent". However, on the report-removal perturbation, ECoCheck detects only 5/30 cases, only one more than Linear (4/30). The author's response does not explain this small gap. If the method cannot reliably detect the case that motivates it, the motivation itself is not well supported. Reviewer A5Hp also mentioned similar questions about the motivation of the paper.

Also, the writing is hard to follow. As Reviewer A5Hp also noted, the paper relies heavily on abstract terminology, and the revision does not substantially improve its readability.

Given these considerations, I have decided to adjust my score down accordingly.

Reviewer_3dz8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ECoCheck, a framework for checking whether agents’ evidence, claims, and actions satisfy task-defined requirements. It considers whether evidence supports a claim, whether a decision follows the evidence and task rules, and whether execution matches a claim. The method constructs an interaction graph, extracts source-linked facts, translates selected requirements into symbolic checks, and provides diagnostic feedback. Experiments evaluate detection on perturbed traces and task outcomes in tool collaboration, coordination, and social simulation.

Critical strengths

S1. The problem formulation captures a meaningful limitation of ordinary factual checking. Evidence appearing somewhere in a system log does not establish that the agent making a claim received the required support. ECoCheck makes ownership, communication, and ordering relevant to the checking task. This is a useful perspective for multi-agent systems, where a correct statement can still violate a required reporting or execution procedure.

S2. The framework provides a concrete connection between interaction records and symbolic checking. Source-linked facts allow the selected evidence to be inspected alongside the encoded requirements and resulting diagnostics. The evaluation considers both recorded detection and downstream task outcomes. The reported improvements, particularly 17/30 versus 6/30 detections for unsupported claims and an 11.11 percentage-point overall goal-success advantage over Linear, are encouraging.

Critical weaknesses

W1. The detection evaluation seems not to sufficiently establish checking accuracy. ECoCheck records more detections than Linear, but the evaluation does not establish which perturbations actually violate a task obligation or report false-positive rates on corresponding clean traces. Therefore it makes it difficult to determine whether the additional detections reflect more accurate checking or not. I suggest a focused evaluation with verified violations and clean controls, which would provide more direct support for the central contribution.

W2. The task-outcome comparisons do not sufficiently isolate the contribution of evidence-linked checking. The Scenario Benchmark treatment includes additional generation and feedback to tool or user simulators, without a guaranteed final recheck. CoLLAB compares against a baseline without verification feedback, while Werewolf combines checking with private-role access and a separate voting recommendation procedure. These comparisons support the usefulness of the complete treatments, however, leave unclear how much improvement comes from the proposed checking method. It would strengthen the empirical case more if a comparison with equivalent information access and generation budget us given.

Questions for authors

Q1. Can the perturbation evaluation distinguish verified task-obligation violations from modifications that leave the trace valid? What are the checker’s false-positive rates on the corresponding clean traces?

Q2. Do any experiments compare ECoCheck with ordinary feedback or refinement under equivalent information access and generation budgets? For Werewolf, is there a comparison giving the baseline the same private information and voting procedure?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 3dz8

Thank you for highlighting the distinction between checking accuracy and downstream task performance.

W1 / Q1: Checking accuracy and clean controls.

Table 3 reports 30 clean-control traces, labeled as satisfying the evaluated task obligations. Each false-positive rate is the number of clean traces flagged by that method divided by 30: 1/30 (3.33%) for ECoCheck and 3/30 (10.00%) for Linear (Sections 4.2 and 5.1). Both counts include the one jointly flagged trace. Verified violation labels for perturbed traces and clean/perturbed pairings are not documented, so the perturbation counts cannot be read as sensitivity.

W2 / Q2: Comparisons with ordinary feedback.

Scenario Benchmark. Section 4.1 distinguishes ordinary LLM refinement (LLM-base), LLM critics that analyze retrieved records directly, and the symbolic variants. Linear-SMT is the original Linear comparator.

TreatmentMacro-average overall GSR
Base36.67%
LLM-base41.11%
Linear-LLM43.33%
Linear-SMT45.55%
Graph-LLM52.22%
ECoCheck56.67%

ECoCheck is 15.55 percentage points above ordinary LLM refinement and 4.45 points above Graph-LLM, using values before display rounding (Section 5.2; Tables 4 and 7). In travel refinement over R0–R3, ECoCheck rises from 53.33% to 60.00%, Graph-LLM from 53.33% to 56.67%, and LLM-base from 50.00% to 53.33% (Table 8).

CoLLAB. On ten meeting-scheduling cases with six agents each, ECoCheck's mean total score rises from 25.7 to 32.1 over R0–R3; ordinary LLM feedback reaches 26.4. Mean overlap penalty falls from 5.4 to zero, compared with 4.0 at R3 under ordinary feedback. All ten ECoCheck cases have zero recorded penalty at R3. Mean coordination reward is maintained while attendance improves (Section 5.3; Table 9; Appendix Figure 7). Both methods have the same recorded R0 score components per case.

These experiments compare complete feedback configurations; the records do not establish equal information access or total generation budgets. In Scenario Benchmark, feedback also regenerates conversations with tool/user simulators, without a guaranteed final recheck (Section 3.4; Table 1).

Werewolf. The results concern private-role access, rule-based target selection, and SMT feedback together (Section 5.4; Appendix B.1). The available experiments do not include a control with the same private information and voting procedure.

Thanks for the rebuttal, which partially addresses my concerns by clarifying the clean-control false-positive rates and comparisons with ordinary LLM feedback. While the verified violation labels and comparisons with matched information access and generation budgets remain unavailable, the current version suggests a useful framework with encouraging empirical results to me. Therefore I would like to keep my weak acceptance score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.