acceptodds
Under review as a conference paper at ICLR 2027

GRAIN: GRANULARITY AND THE VALIDITY GAP IN LLM-AGENT CONSENSUS

Abstract

Byzantine validity requires that a value proposed by every honest participant be decided, and it treats each honest proposal as a fixed input. A language-model agent's proposal is a random draw, and whether two draws count as the same proposal depends on the grain at which outputs are compared. The validity clause is therefore triggered only when all honest proposals collide, an event whose probability falls as the grain gets finer; single-agent samples predict pre-interaction live-group agreement with no fitted parameter. We prove that, as groups grow, a sound observer certifies the honest mode with probability tending to one below a fault fraction of and to zero above it, where is the honest top-two margin; the classical one third is the deterministic case. Under conditionally independent honest labels and a common view, the honest mode on three models is certified at the classical budget with mean probability only 0.84 even when only final answers are compared; on 24 annotated model–task cells, coverage at the human-judged grain of the stated decisive operation is about half its answer-grain value (0.43 versus 0.82; 95% interval 0.27–0.61). Measuring finer grains is itself unreliable: exact string matching splits 97% (weighted) of pairs that humans judge equivalent, while LLM judges reproduce plain answer equality. Prompted “Byzantine” agents, too, carry out their assigned attack to very different degrees across models. We close with a reporting checklist for consensus claims over stochastic agents.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, Byzantine fault tolerance, consensus validity, agreement granularity, collision probability

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_MnNTOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper mainly investigates how the randomness of LLM agent outputs and different levels of agreement granularity affect the validity of traditional Byzantine Fault Tolerance in multi-agent systems. The authors examine three main aspects: how often the validity condition is triggered, how reliably honest agents' answers can be certified, and how accurately different tools measure agreement. They also provide theoretical analysis to explain the relationship between agreement granularity, output distributions, and fault-tolerance thresholds. The experiments cover benchmarks such as GSM8K, MMLU, and MBPP, using different language models, adversarial agent interventions, and human annotations for validation. The results show that different levels of agreement granularity can significantly change agreement probabilities and certification outcomes. They also find that simple text matching and LLM judges struggle to accurately identify whether agents use the same reasoning steps.

Critical strengths
  1. The paper provides a useful theoretical perspective by connecting agreement granularity with the randomness of LLM agent outputs, showing how output distributions affect agreement probabilities and fault-tolerance thresholds, which I think helps explain why traditional BFT validity conditions may become less informative in multi-agent systems.

  2. The experiments are quite comprehensive, covering multiple benchmarks, different models, adversarial agents, and also like human annotations, and I particularly like how the authors examine the limitations of Exact String Matching and LLM Judges, showing that these methods may fail to accurately capture agreement in reasoning steps.

Critical weaknesses
  1. I think the theoretical novelty of the paper needs further clarification. Some of the certification criteria in Section 4.2 are based on prior work, while the derivations of collision probabilities and fault-tolerance thresholds mainly rely on classical probability analysis. Also, these results depend on specific assumptions, such as independent sampling and a common view, and do not directly apply to general BFT protocols. I think the authors should better explain what new theoretical contributions this paper makes compared to existing studies.

  2. The experimental validation of fine-grained agreement is still somewhat limited. In Section 6.3, human annotators judge whether reasoning steps are equivalent based only on the final answers and short KEY summaries, without seeing the full reasoning process. Also, the direct fine-grained partitioning experiment covers only 24 model–task configurations, and the inter-annotator agreement for reasoning operations is relatively moderate (κ = 0.532). I think these limitations may affect the reliability of the fine-grained agreement measurements.

  3. Some of the statistical estimation methods need further clarification. In Appendices B and G, the authors use the empirical mode from the samples to calculate the corresponding U-statistic and describe it as an unbiased estimator. However, selecting the mode and estimating its probability from the same samples may introduce selection bias. I think the authors should clarify this issue and explain whether it could affect the reported certification coverage results.

Questions for authors
  1. Could the authors further clarify the main theoretical novelty of this work compared to existing studies, especially regarding the certification criteria and the derived fault-tolerance threshold?

  2. In Section 6.3, human annotators only see final answers and short KEY summaries rather than full reasoning traces. How do the authors ensure that these summaries accurately represent the agents' actual reasoning steps, and could this affect the reported agreement results?

  3. In Appendices B and G, the empirical mode is selected and evaluated using the same samples. Could this introduce selection bias into the U-statistic estimates, and how might it affect the reported certification coverage?

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

This paper addresses consensus in LLM agents. Specifically, the authors argue that whether two samples count as the same depends on the granularity at which they are judged. For example, are they judged based on the final answer or also the reasoning steps to get there. As more agents are added or as granularity increases, consensus decreases. The authors formalize this and prove that the share of faculty agents and groups that can tolerate depends on the agents' top answer and how much they favor it. They test this across three OpenAI models and provide a reporting checklist for judging consensus claims in LLM agents

Critical strengths

The paper makes a simple but important point that, as far as I know, hasn't been stated this clearly before. I also found the reporting checklist practical, and I appreciated that the paper keeps agreement, validity, and correctness separate rather than letting them blur together.

The authors take the measurement problem seriously, and what they find is useful in its own right. Agreement numbers are only as good as the tool that decides whether two outputs are “the same.” The authors test several such tools against careful human annotation and find that none of them measure what is intended.

Critical weaknesses

Most of the theoretical content seems pretty simple, with the key empirical prediction close to guaranteed by construction.

The dramatic fine-grain results depend on a matching rule the authors themselves show is invalid.

Questions for authors

The theory assumes each agent's proposal is independent of the others, which holds only before they start communicating. What happens when one assumes multiple rounds, which is more common?

Can you provide a concrete example of where agreement on the answer would mislead and agreement on the reasoning step is what you actually need?

The paper reads as very dense. Many numbers appear before the definitions are in place.

1 comment

I appreciate the authors’ responses but I still question the novelty and contribution and thus maintain my current score.

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

The paper asks what the Byzantine validity clause ("if every honest participant proposes v, v is decided") means when the participants are LLM agents. Their proposals are random samples, and whether two proposals count as "the same" depends on a chosen equivalence relation, which the authors call the grain. Under that view, the clause's condition is a collision event with probability Σ p(c)^h. That probability falls geometrically in h and can only fall as the grain gets finer. The authors then show that certifying from a shared histogram needs an honest margin above 2f, and they derive a fault threshold β* = Δ/(2+Δ). Coverage at n = 10, f = 3 is 0.843 at the answer grain, about 0.43 at a human-judged "decisive operation" grain, and close to zero at a lexical grain.

Critical strengths
  1. The central conceptual point is well formulated.The framing is useful, the statement is clean.
  2. The human calibration in Appendix G is well designed.It uses a pre-specified stratified frame, inverse-probability weights, Fleiss' κ per axis, unresolved pairs kept out of the error denominators rather than quietly counted as DIFF, and a sanity check of the bounding estimator against the known answer-grain value. 3.The comparison between forced and prompted attackers (Table 5) makes a point the field needs. The prompted Opus attacker adopted its target in only 10 of 288 slots, so claims that a system "tolerates f attackers" aren't comparable across models unless the realized attack is reported. 4.The authors are also careful about what they don't claim.
Critical weaknesses

1.The threshold in the theory says little at the group sizes actually used. At n = 3f+1, certification reduces to honest unanimity on the mode (Remark 6). So the headline 0.843 is just the Q1 collision quantity at h = 7, and β* adds no information at the n tested. 2.The scope is narrow: three small models from one vendor, all sampled at temperature 1.0. Temperature directly controls dispersion, and a sweep at the answer grain would be cheap. The threat model also covers round 0 only, which leaves out persuasion, the attack that matters most in debate. 3.The "parameter-free" prediction of live groups (Table 4) looks close to a consistency check. Round-0 replies are independent samples taken before any interaction, so Prop. 1 predicts them by construction unless the prompts differ.

Questions for authors

1.Live-group prediction (Table 4): Is the round-0 debate prompt the same as the prompt used for the single-agent replies? Were the two sets of samples collected at different times? What would it have meant if the prediction had failed? 2.Judge baselines: How do the judges behave if the final answers are hidden and they see only the KEYs? Did you try a stronger judge, such as the Opus model used elsewhere in the paper, or bidirectional NLI entailment as in semantic entropy? 3.Temperature: How do Tables 1 and 2 change at temperatures 0.3 and 0.7? 4.Prompted Opus attacker (Table 5): At f = 1 the attacker adopts the target in 0 of 48 slots, yet all-participant unanimity is 0.667. What did the attacker output in the other third of trials: the gold answer, a third answer, or something unparseable? 5.MBPP checker: Does the acceptance check compare against the gold return value, or against the benchmark's test asserts?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.