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

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 $A(h)={\sum }_{c}p(c{)}^h$ 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 $\Delta /(2+\Delta )$ and to zero above it, where $\Delta$ 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.