{"id":"8c3aef3d-88a9-4ab4-958a-3375b658e2de","arxiv_id":"2605.05020","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Graph-SND replaces the complete pairwise average in System Neural Diversity with a weighted average over graph edges, recovering the original metric exactly when the graph is complete and providing linear-cost sparse and sampling-based variants with theoretical bounds and empirical speedups.","lead":"The paper introduces Graph-SND, which measures behavioral diversity among AI agents by averaging distances over edges of a chosen graph instead of every possible pair. This change keeps the original meaning while cutting computation time from quadratic to linear in team size, with proofs and tests showing it works for both measurement and control.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption targets low-rank/expander structure needed for some distortion proofs, but the paper supplies an unconditional probabilistic bound for random d-regular graphs that bypasses that assumption, and the reported experiments directly use such graphs with near-exact empirical recovery. The abstract-only limitation is real for full proof verification, yet the combination of exact recovery, unbiased estimator, and concrete scaling results leaves no load-bearing gap in the central claim.","tokens_in":1967,"tokens_out":339,"duration_ms":45236,"concrete_test":"Recompute the relative error SND_G^u / SND on the n=100 Bernoulli-0.1 and random d-regular cases from the VMAS runs using the exact distance matrices collected during the 500-iteration PPO training; if the observed ratio deviates outside [0.998, 1.002] on more than 5% of iterations, the practical approximation claim weakens.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Graph-SND recovers SND exactly on K_n, provides an unbiased estimator under random edge sampling, and yields controlled distortion (expanders, spectral low-rank, and unconditional O(D_max/sqrt(n)) for random d-regular graphs) so that the sparse version can serve as a drop-in replacement. The provided abstract and reader summary indicate that exact recovery, unbiasedness, concentration, and empirical tracking are shown on VMAS, with closed-loop control experiments confirming indistinguishable reward outcomes. No internal inconsistency in the regimes or unaddressed assumption appears to undermine the argument that semantics are preserved at the reported scales.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces Graph-SND, which generalizes System Neural Diversity (SND) by replacing the quadratic complete-graph average of pairwise behavioral distances with a weighted average over the edges of an arbitrary graph G. It establishes exact recovery of SND when G = K_n, an unbiased Horvitz-Thompson estimator under random edge sampling with O(1/sqrt(m)) concentration, forwarding-index distortion bounds for expanders, a spectral refinement under low-rank distance structure, and an unconditional probabilistic O~(D_max/sqrt(n)) bound for random d-regular graphs. Experiments on VMAS verify recovery, unbiasedness, concentration, and scaling (including 10x speedup at n=100 and up to n=500), while DiCo closed-loop diversity control at n=50 shows indistinguishable reward outcomes with ~9.5x cost reduction; random d-regular expanders empirically achieve ratios in [0.9987, 1.0013].","tokens_in":2114,"tokens_out":643,"duration_ms":27940,"significance":"If the stated theorems hold, the work removes the quadratic aggregation bottleneck in SND while preserving semantics, enabling diversity measurement and control at larger team sizes in MARL. Strengths include the exact-recovery guarantee, unbiased estimator, explicit distortion bounds (expanders, spectral, unconditional regular-graph), and reproducible empirical tracking on VMAS/PettingZoo and DiCo with closed-loop verification. This combination of parameter-light theory and scaling experiments positions the method as a practical drop-in replacement.","major_comments":[{"comment":"Abstract (theorems paragraph): the unconditional probabilistic bound O~(D_max/sqrt(n)) for random d-regular graphs is load-bearing for the claim that sparse Graph-SND remains faithful at scale; the manuscript should state the precise theorem (including any hidden constants or logarithmic factors) and the proof sketch, as the current summary invokes standard expander properties without showing how they combine with the distance matrix to yield this rate.","section":"Abstract"},{"comment":"Spectral refinement and expander sections: the distortion bounds invoke low-rank or expander-friendly structure on the distance matrix, yet the VMAS experiments report only aggregate ratios without reporting the observed rank or eigenvalue decay of the distance matrices; this leaves the applicability of the refinement bounds unverified for the tested regimes.","section":"Spectral refinement and expander sections"}],"minor_comments":[{"comment":"Notation: the symbols SND_G^u and the precise weighting scheme for arbitrary G should be defined at first use in the introduction rather than deferred to the methods section.","section":"Introduction"},{"comment":"Experiments: the PettingZoo TVD panel and the nine matched DiCo cells would benefit from explicit reporting of the number of random seeds and the exact statistical test used to declare reward differences 'indistinguishable from zero'.","section":"Experiments"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript fits well within the scope of a machine-learning venue focused on RL scalability; the citation pattern appears standard and does not raise novelty concerns."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive evaluation and the recommendation of minor revision. The two major comments identify opportunities to improve the precision of the theoretical claims and the empirical verification of the underlying assumptions. We address each comment below and will incorporate the requested clarifications and analyses in the revised manuscript.","responses":[{"response":"We agree that a more explicit statement strengthens the abstract. The current use of the tilde-O notation hides polylogarithmic factors that arise from the expander mixing time and the concentration bounds applied to the distance matrix. In the revision we will update the abstract to state the bound as O~(D_max polylog(n)/sqrt(n)) and will add a concise proof sketch in the main theoretical section on random d-regular graphs. The sketch will explicitly combine the forwarding-index distortion for d-regular expanders with the maximum distance D_max via the spectral gap to obtain the stated rate, making the derivation transparent.","revision_made":"yes","referee_comment":"[Abstract] Abstract (theorems paragraph): the unconditional probabilistic bound O~(D_max/sqrt(n)) for random d-regular graphs is load-bearing for the claim that sparse Graph-SND remains faithful at scale; the manuscript should state the precise theorem (including any hidden constants or logarithmic factors) and the proof sketch, as the current summary invokes standard expander properties without showing how they combine with the distance matrix to yield this rate."},{"response":"This observation is correct and points to a useful addition. To verify that the low-rank and expander-friendly assumptions hold in the regimes tested, we will augment the VMAS experimental section with an analysis of the behavioral distance matrices. We will report the effective numerical rank (eigenvalues above a small threshold) and the eigenvalue decay profiles for representative distance matrices drawn from the VMAS environments. These diagnostics will allow readers to assess the applicability of the spectral refinement and expander bounds to the observed approximation ratios.","revision_made":"yes","referee_comment":"[Spectral refinement and expander sections] Spectral refinement and expander sections: the distortion bounds invoke low-rank or expander-friendly structure on the distance matrix, yet the VMAS experiments report only aggregate ratios without reporting the observed rank or eigenvalue decay of the distance matrices; this leaves the applicability of the refinement bounds unverified for the tested regimes."}],"tokens_in":1684,"tokens_out":495,"duration_ms":57654,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper shows a way to compute System Neural Diversity using sparse graphs instead of all pairs, which drops the cost a lot while keeping the numbers close. What they did new is define Graph-SND as a weighted average over graph edges, with exact match when the graph is complete. For fixed sparse graphs they give distortion bounds using expander properties and spectral stuff for low-rank cases. For random sampling they use Horvitz-Thompson to get unbiased estimates with concentration. They also have a bound for random regular graphs without conditions. The VMAS tests confirm the math works in practice, and the DiCo experiment shows diversity control still hits the targets with the same rewards but much less compute per step. The work is solid on the practical side. The speedups are real, around 10x, and the metric stays within a tiny range of the full version in the random graph case. They credit the standard tools from graph theory and sampling, which is fair. A couple soft spots: the bounds lean on the distances having some nice structure, and the experiments only check a few environments, so it might not hold everywhere. Also, picking the right graph or sampling rate could be tricky in new settings. The abstract claims the theorems but I'd want to see the full proofs to be sure about the unconditional bound. This is for MARL folks who need diversity metrics at scale, like in large team training or control. A reader working on implementation would get immediate value from the drop-in replacement. It should go to a serious referee since the claims are testable and the results look promising for the subfield. I'd say send it for peer review.","headline":"Graph-SND turns the quadratic SND into a linear-cost graph version with good theoretical and empirical support for keeping the same behavior.","tokens_in":2614,"tokens_out":398,"would_cite":true,"duration_ms":51948,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Graph-SND measures behavioral diversity in agent teams by averaging distances only over edges of a chosen graph rather than every pair.","keywords":["Graph-SND","behavioral diversity","multi-agent reinforcement learning","sparse aggregation","Horvitz-Thompson estimator","system neural diversity","graph expanders","diversity control"],"falsifier":"Compute both full SND and Graph-SND on teams of 100 agents whose behaviors produce a distance matrix without low-rank structure and check whether their ratio deviates from 1 by more than the stated O(D_max / sqrt(n)) bound with higher probability than predicted.","tokens_in":2853,"feed_emoji":"","tokens_out":798,"duration_ms":42410,"temperature":0.7,"pith_summary":"The paper shows that the full pairwise average used in SND for team behavioral heterogeneity can be replaced by a weighted average over the edges of any graph G. When G is the complete graph this recovers SND exactly, while a sparse fixed G reduces the cost to linear in the number of edges and random edge sampling produces an unbiased estimator with concentration guarantees. The authors prove distortion bounds for expander graphs and low-rank distance matrices, plus an unconditional probabilistic bound for random regular graphs. Experiments on VMAS environments confirm that the sparse version tracks the full metric closely while cutting per-call time by roughly a factor of ten and supporting diversity control loops at larger team sizes.","feed_headline":"Sparse graph replaces full pairwise average for agent diversity","feed_subtitle":"Graph-SND averages behavioral distances over selected edges, recovers the original metric exactly on the complete graph, and cuts cost by 10","key_machinery":"Graph-SND, the weighted average of pairwise behavioral distances taken only over the edges of an arbitrary graph G","core_discovery":"Graph-SND replaces the complete-graph average of SND with a weighted average over the edges of an arbitrary graph G. It recovers SND exactly when G equals the complete graph K_n, defines a localized O(|E|) measure for any fixed sparse G, and yields an unbiased Horvitz-Thompson estimator for random edge samples. For fixed sparse graphs the paper proves forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure; for random d-regular graphs it proves an unconditional probabilistic bound of order O(D_max / sqrt(n)).","pith_inferences":["The same edge-sampling idea could be applied to other pairwise statistics in multi-agent settings such as cooperation or conflict measures.","Random regular expanders at Theta(n log n) edges appear sufficient for near-exact recovery even without assuming low-rank structure on the distances.","The speedup factor of order binom(n,2)/|E| suggests the method remains practical up to team sizes of several hundred agents on current hardware.","If the distance matrix is approximately low-rank in real tasks, even fewer edges than the expander bound may suffice."],"forward_implications":["Diversity measurement becomes linear in the number of edges for any fixed sparse graph instead of quadratic in team size.","Random edge sampling produces an unbiased estimator whose error concentrates as O(1/sqrt(m)) in the number of samples m.","Expander graphs and low-rank distance matrices keep the sparse approximation within explicit distortion bounds.","A Bernoulli-0.1 edge sample matches full SND within 0.13 percent while cutting metric time by about 10x in n=100 PPO runs.","The same sparse measure can be dropped into closed-loop diversity control without changing the underlying semantics."],"fun_headline_variants":["Graph-SND replaces full SND with sparse graph edge averages","Graph-SND scales diversity metrics linearly with graph sparsity","Arbitrary graphs enable exact SND recovery at low computation cost","Graph-SND provides unbiased SND estimator via edge sampling"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The matrix of distances between agent behaviors has enough low-rank or expander-friendly structure that averages over a sparse or sampled graph stay close to the full pairwise average.","fun_headline_variants_meta":{"raw":{"variants":["Graph-SND replaces full SND with sparse graph edge averages","Graph-SND scales diversity metrics linearly with graph sparsity","Arbitrary graphs enable exact SND recovery at low computation cost","Graph-SND provides unbiased SND estimator via edge sampling"]},"model":"grok-4.3","cost_usd":0.01171,"raw_usage":{"total_tokens":5233,"prompt_tokens":883,"num_sources_used":0,"completion_tokens":63,"cost_in_usd_ticks":117099500,"prompt_tokens_details":{"text_tokens":883,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4287,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":883,"tokens_out":63,"duration_ms":29487,"temperature":1.0,"reasoning_tokens":4287,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-08T16:34:44.872341+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Compute both full SND and Graph-SND on teams of 100 agents whose behaviors produce a distance matrix without low-rank structure and check whether their ratio deviates from 1 by more than the stated O(D_max / sqrt(n)) bound with higher probability than predicted.","supporting_citations":[],"review_version":1}