{"id":"64aabc22-4836-4c84-b122-40d788d321b1","arxiv_id":"2502.06751","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The authors define mixing time and minimax fidelity for feedforward graphs, use them to design a recursive sparse graph (FS) with polylogarithmic mixing time, and show it matches dense attention on parity and retrieval tasks.","lead":"The paper proposes two measures, mixing time and fidelity, for judging how well a directed feedforward graph lets information flow to a final decision node. It then uses these measures to design a new sparse graph that matches dense attention on some tasks while using fewer connections.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The constant-α hypothesis in Theorem 6.1 is unsatisfiable for the recursive FS graph: with D≈log n/log log n levels, any node's minimum cross-block edge fraction is at most 1/D→0, so the O(polylog n) mixing-time proof does not apply to the constructed graphs.","rationale":"The reader's weakest assumption focuses on whether minimax fidelity predicts trained attention performance. That is a real limitation, but the more concrete and directly load-bearing issue is the proof of Theorem 6.1, which the reader mentioned only as 'a gap.' The constant-α assumption is not merely unproved; it is impossible to satisfy for a graph with D→∞ recursive levels and finite outdegree. Since the FS generator is defined precisely by this recursive block structure, the paper's headline theoretical guarantee does not follow for the graphs it is meant to cover. The empirical mixing-time measurements in Figure 1 may still be correct, and a modified argument with level-dependent α_d=Θ(1/D) would likely restore a polylog bound, so the overall message is not necessarily destroyed. But the stated theorem is vacuous as written. This strengthens the case for the reader's CONDITIONAL verdict: the paper should be accepted only if the mixing-time proof is repaired and the generator's parameters are specified, alongside the already-requested code release. I therefore do not change the verdict, but I identify the proof gap as the single most load-bearing technical concern.","tokens_in":18747,"tokens_out":20082,"duration_ms":185335,"concrete_test":"Analytically derive min_{v,i} e_i(v)/T(v) for the FS generator with total outdegree O(log n). Since Σ_i e_i≤T, min_i e_i/T≤1/D, and D=⌈log n/log⌈log n⌉⌉→∞, so the constant-α assumption cannot hold for large n. Numerically, instantiate the recursive FS generator from Section 6 and Figure 2 (right) for n=2^10, 2^20, 2^30 with indegree c log n, and compute the minimum over all nodes and levels of the fraction of outgoing edges that cross blocks; if this minimum decays to zero as n grows, Theorem 6.1's hypothesis fails for the actual construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 6.1 assumes that for every node, the proportion of its outgoing edges that go across blocks is lower-bounded by a constant α>0. In the FS generator, each node lies in nested blocks at D≈⌈log n/log⌈log n⌉⌉ levels, and to reach the sink it must cross to the next block at each level. Let e_i(v) be the number of cross-block outgoing edges from node v at level i, and let T(v)=Σ_i e_i(v) be its total outdegree (ignoring self-loops). If e_i(v)/T(v)≥α for every i, then T(v)≥Σ_i αT(v)=DαT(v), forcing Dα≤1. Since D grows without bound with n, no constant α>0 can exist for any finite-outdegree graph. Remark C.1 attempts to satisfy the assumption via geometric decay e_i=δ_0 r^i, but at the deepest level δ_0 r^D=δ_0 n^{log r/log log n}→0; the required edge count becomes fractional and eventually less than 1, so the construction is not realizable as an integer graph with O(log n) outdegree. Thus the key hypothesis of the theorem is vacuous for the very graphs the theorem claims to analyze, and the stated O(polylog n) mixing-time guarantee is unproven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies feedforward computational graphs (directed graphs with edges only from earlier to later nodes) through two proposed measures: averaged mixing time, which tracks how quickly a lazy random walk reaches the sink node, and minimax fidelity, which tracks how sharply a node's feature can be recovered at the sink under mean-aggregation diffusion. The authors analyze these measures for line graphs, fully connected graphs, Erdős–Rényi graphs, oriented expanders, Poisson(p) graphs, and a new recursive graph family discovered via FunSearch (FS graphs). They prove that the line graph has O(n) averaged mixing time and high normalized fidelity, while the fully connected graph has O(log n) mixing time but normalized fidelity equal to 1. For the FS graphs they state a theorem claiming O(polylog n) mixing time under a constant-α assumption on cross-block edge proportions. Empirically, they train graph attention networks on maximum, second-maximum, and parity tasks, and report that FS graphs match or exceed the performance of other sparse graphs and sometimes approach the fully connected graph.","tokens_in":19078,"tokens_out":10301,"duration_ms":87197,"significance":"If the theoretical claims were fully established, the paper would offer a useful, task-agnostic design principle for sparse feedforward graphs in attention-based models, complementing recent work on over-squashing and under-reaching. The proposed metrics are defined independently of experiments, and the asymptotic analyses for line and fully connected graphs are correct and clearly presented. The empirical evaluation is careful and covers length generalization up to 1024. However, the central theoretical guarantee for the discovered FS graphs (O(polylog n) mixing time) depends on a condition that appears impossible to satisfy for the recursive construction, so the main theoretical contribution is currently not supported. The paper would be strengthened by a corrected theorem or by honestly presenting the mixing time of FS graphs as an empirical observation.","major_comments":[{"comment":"The constant-α hypothesis of Theorem 6.1 is not satisfiable by the recursive FS graph for growing n. Let D ≈ ⌈log n / log⌈log n⌉⌉ be the number of recursive levels and let e_i(v) be the number of cross-block outgoing edges of node v at level i, with total outdegree T(v) = Σ_i e_i(v). If e_i(v)/T(v) ≥ α > 0 for all i, then summing over i gives T(v) ≥ D α T(v), so D α ≤ 1. Since D → ∞, no positive constant α can exist in any family with bounded outdegree. Remark C.1's proposed geometric decay δ_0 r^i yields, at the deepest level, δ_0 r^D = δ_0 n^{log r / log log n} → 0; for large n this is below 1 and cannot be realized as an integer number of edges. Consequently the proof in Appendix C does not apply to the graphs generated by the FS generator, and the claimed O(polylog n) mixing time is unproven as stated.","section":"6.1, Theorem 6.1, Remark C.1"},{"comment":"The FS generator is described informally ('full bipartite graphs across successive chunks', 'concatenating κ random perfect matchings', 'fill intra-cluster edges recursively'), and the proof of Theorem 6.1 abstracts each level as a chain of ⌈log n⌉ blocks with a fixed crossing probability α. The paper never specifies the precise construction—e.g., how many edges each expander contributes to each node, how recursion terminates, and how the 'geometric decay' of Remark C.1 is implemented with integer degrees—so the reader cannot check whether the assumptions of the theorem hold for the graphs actually evaluated in Figure 1 and Section 7. A precise, implementable definition of the FS generator is needed before the mixing-time claim can be assessed.","section":"Section 6 / Appendix C"},{"comment":"The claim that the two metrics 'correlate' with trained model performance is supported only by visual inspection of Figure 3. No correlation coefficients, error bars, or statistical tests are reported. Because the FS graph was selected by optimizing fidelity subject to a mixing-time budget, the practical significance of the framework depends on this correlation being meaningful. The authors should provide a quantitative comparison, e.g., rank correlation between metric-based rankings and test accuracy across graph families at matched in-degree budgets, or clearly label the empirical match as qualitative.","section":"Section 7, Figure 3"}],"minor_comments":[{"comment":"The word 'probabilty' should be 'probability'.","section":"Section 4.3.1"},{"comment":"The summation in (Δx)_j = Σ_j Δ_{ij} x_j should run over i (the incoming nodes), not over j; as written it is dimensionally inconsistent.","section":"Section 5.1, Eq. (3)"},{"comment":"Equation (6) is mis-rendered; the intended expression is max_a binom(a, n-1)/2^a (see Appendix B), not the fraction 'a/(n-1)' shown in the text.","section":"Section 5.2.2, Eq. (6)"},{"comment":"The figure has no legend identifying which curve corresponds to which graph generator; the caption should list the generators and their plotting styles.","section":"Figure 1"},{"comment":"The phrase 'casual attention mask' should be 'causal attention mask'.","section":"Appendix E.1"},{"comment":"The word 'alowing' should be 'allowing'.","section":"Impact Statement"},{"comment":"The graph name 'Erd s-Rényi' should be 'Erdős–Rényi'.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the ICML audience, and the empirical study is solid. However, the main theorem's assumption appears vacuous for the proposed FS construction, leaving the central theoretical claim unsupported. The authors should be asked to fix the theorem or reframe the mixing-time guarantee as an empirical finding. The metric definitions and the analyses of line and fully connected graphs are sound and can remain."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take on arXiv:2502.06751. The paper proposes two complementary metrics for feedforward computational graphs—averaged mixing time and minimax fidelity—and uses them to design a sparse recursive graph (FS) that empirically rivals dense attention on parity and max retrieval. That part is genuinely nice. The metrics are well-defined, the asymptotic computations for line and fully connected graphs are correct, and the empirical study is careful and honest.\n\nThe soft spot is Theorem 6.1, the claimed O(polylog n) mixing time bound for the FS graph. The theorem assumes that every node has a constant fraction α of its outgoing edges crossing blocks at each recursion level. But with D ≈ log n / log log n levels, if each level's share of a node's total outdegree were at least α, then total outdegree would be at least D α times itself, so D α ≤ 1, which forces α ≤ 1/D. No constant α works. Remark C.1 tries to fix this with geometric decay of edge counts across levels, but that makes the fraction at the deepest levels decay like r^d, not a constant. So the hypothesis is unsatisfiable for the constructed graphs, and the proof as written does not actually establish the bound. This is not a minor gap; it is the main theoretical result of the paper.\n\nThat said, I would not throw the paper out. The empirical story is strong: the FS graph matches fully connected on parity while using far fewer edges, and the metrics give a plausible explanation. The fidelity-performance link is demonstrated only empirically, but the tasks are chosen to stress sharpness and mixing, so the evidence is suggestive. The absence of code is a reproducibility nuisance, not a fatal flaw.\n\nMy bottom line: send it to review, but the referee should insist on either a corrected proof (perhaps a bound with a decaying α that still yields polylog mixing) or a demotion of the mixing-time claim to a conjecture. The two metrics are worth having regardless, and the FS graph deserves attention. This is a paper I would bring up in reading group.","headline":"Interesting metrics and a promising sparse graph, but Theorem 6.1's constant-alpha assumption is unsatisfiable for the recursive construction, so the central mixing-time guarantee is unproven as written.","tokens_in":19581,"tokens_out":5998,"would_cite":true,"duration_ms":51964,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C81","05C80","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two complementary measures—averaged mixing time and minimax fidelity—determine whether a feedforward computational graph serves a neural network well, and a recursively built sparse graph achieves the best known trade-off.","keywords":["feedforward computational graphs","causal attention masks","mixing time","minimax fidelity","graph attention networks","length generalization","sparse transformers","graph rewiring"],"falsifier":"Train the paper's graph-attention architecture on a held-out battery of, say, fifty feedforward graph generators with matched in-degree budgets, measure averaged mixing time and normalized minimax fidelity for each, and regress out-of-distribution accuracy on the second-maximum and parity tasks against the two metrics; if the metric-ordering does not reproduce the empirical ranking, the claims that these measures capture graph quality are refuted. A sharper version would compute the same two quantities using the trained models' attention matrices instead of the uniform $\\Delta$, and check whether the ranking survives.","tokens_in":18579,"feed_emoji":"🕸️","tokens_out":12429,"duration_ms":104526,"temperature":0.7,"pith_summary":"The paper proposes that a feedforward computational graph—the directed, time-respecting pattern of connections allowed by a causal attention mask—is good when two complementary quantities are good: the averaged mixing time, which measures how quickly a random walk from any node concentrates on the final sink, and the minimax fidelity, which measures how sharply the weakest node's information can still be read at the sink under averaging diffusion. If this pair of measures is right, sparse causal graphs can be designed by optimizing two numbers rather than by defaulting to fully connected attention or local sliding windows. The authors analyze standard families, show that line graphs and fully connected graphs sit at opposite extremes, and use program search to discover a recursively constructed family, the FS graph, that provably mixes in polylogarithmic time while keeping normalized minimax fidelity above that of a fully connected graph. In trained graph-attention models on maximum, second-maximum, and parity tasks, the FS graph matches or beats other sparse graphs and matches full attention on parity while using substantially fewer edges.","feed_headline":"Sparse recursive graph rivals full attention on causal tasks","feed_subtitle":"Mixing time and minimax fidelity pick a sparse graph that rivals full attention with far fewer edges.","key_machinery":"The central objects are two dual matrices built from the adjacency matrix of a feedforward graph: the row-normalized walk matrix $W$ and the column-normalized averaging-diffusion matrix $\\Delta$. Averaged mixing time is the smallest $t$ such that the average over starting vertices of $\\|W^t e_i - \\mathbf{1}_\\tau\\|_1$ is below $1/4$; it measures how quickly a random walk concentrates on the sink. Minimax fidelity is $\\min_i \\max_t \\Delta^t_{\\tau i}$, the smallest over nodes of the largest coefficient that node ever contributes to the sink after averaging diffusion, and normalizing by $n$ sets the fully connected graph to $1$. The construction carrying the argument is the FS graph: $O(\\log n)$ blocks per recursion level, sparse bipartite expanders between consecutive blocks, and recursive FS graphs inside each block, giving self-similarity and bounded in-degree. Theorem 6.1's proof tracks the expected time to cross $D = \\lceil \\log n / \\log \\log n \\rceil$ recursive levels with a binomial tail bound, establishing $O(\\log^2 n / \\log \\log n)$ mixing time.","core_discovery":"On its own terms, the paper establishes that the two measures are complementary because they arise from two dual normalizations of the adjacency matrix: the walk matrix $W$, normalized by out-degree, controls how fast information travels; the diffusion matrix $\\Delta$, normalized by in-degree, controls how sharply it arrives. It proves that the fully connected graph has logarithmic averaged mixing time but normalized minimax fidelity exactly $1$, line graphs have the reverse profile, and oriented Erdős–Rényi and oriented expander graphs perform poorly on both measures. The constructive discovery is the FS graph generator: split the nodes into $O(\\log n)$ blocks, connect consecutive blocks with bipartite expanders built from random perfect matchings, and recursively fill each intra-block triangle with a smaller copy of the same graph. Theorem 6.1 shows that, whenever every node keeps at least a constant fraction of its outgoing edges crossing blocks, the averaged mixing time is $O(\\mathrm{polylog}\\,n)$, with the proof yielding $O(\\log^2 n / \\log \\log n)$, while the normalized minimax fidelity remains above that of the fully connected graph. Empirically, graph attention networks trained on the FS graph generalize from length 256 to length 1,024 better than other sparse graphs and match the fully connected graph on the parity task.","pith_inferences":["A reader could go further and treat the two metrics as a Pareto front: among random graph generators with the same in-degree budget, the ones dominating on both mixing time and fidelity should also dominate empirically, a claim that is testable outside the paper's graph families.","Because minimax fidelity tracks the sharpest possible extraction of a single node at the sink, the framework naturally extends to long-context retrieval benchmarks; one could test whether recursive FS masks improve needle-in-a-haystack tasks in large language models.","The paper fixes one graph for all layers and only mentions layer-varying graphs as future work; a natural extension is to let the mask change across depth, with the same two metrics evaluated on the product of per-layer graphs.","The fidelity model assumes uniform averaging diffusion, so replacing $\\Delta$ with measured trained-attention transitions would show whether the metrics remain predictive when attention is learned rather than uniform."],"forward_implications":["If the two measures are right, the fully connected causal mask is not the gold standard: it has logarithmic mixing time but the lowest normalized fidelity, so sparse alternatives can dominate it on both axes.","The recursive block-expander template gives a concrete recipe for building sparse causal masks with polylogarithmic mixing time and self-similar structure, replacing hand-tuned sliding windows.","Graphs with the same mixing-time and fidelity profile should behave similarly in practice, so causal-attention designs can be screened by these two numbers before any training.","Training on sequences up to length 256 and testing to length 1,024, the FS graph's out-of-distribution accuracy is competitive with full attention, indicating sparsification by these principles does not sacrifice length generalization.","Fine-tuning a 2-billion-parameter language model with the FS graph as attention mask reaches perplexity comparable to full attention on Wikipedia text, suggesting the design can cut computational cost in realistic language modeling."],"supporting_citations":[{"why":"Supplies the FunSearch program search that discovered the initial $O(\\log n)$-block motif from which the FS graph generator is derived.","marker":"Romera-Paredes et al., 2023"},{"why":"Provides the over-squashing theorem and in-degree limitation that motivate limiting each node's incoming edges.","marker":"Barbero et al., 2024"},{"why":"Defines the dispersion problem and the maximum-retrieval task used to argue that high in-degree harms sharp propagation.","marker":"Veličković et al., 2024"},{"why":"Supplies the averaged mixing time notion that the paper adopts as its first measure.","marker":"Espuny Díaz et al., 2024"},{"why":"Gives the under-reaching phenomenon, which the paper invokes to justify mixing time as a cutoff.","marker":"Barceló et al., 2020"},{"why":"Shows over-squashing limits GNN power and that fully connected undirected graphs are not optimal for commute time, an analogy the paper uses against the feedforward star.","marker":"Di Giovanni et al., 2024"},{"why":"Provides the bipartite expander construction from random perfect matchings used for the FS graph's inter-block connections.","marker":"Lubotzky, 1994"},{"why":"Provides the companion explicit expander construction used to turn inter-block chunks into sparse bipartite expanders.","marker":"Sarnak, 1990"},{"why":"Supplies the graph attention network architecture used in the empirical comparisons.","marker":"Veličković et al., 2018"}],"fun_headline_variants":["Fidelity and mixing time define good feedforward graphs","FS graph: sparse recursive design matches full attention","Graph metrics predict feedforward network performance","New graph generator rivals full attention with fewer edges","Two complementary measures guide feedforward graph design"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that minimax fidelity, computed under a uniform averaging-diffusion model, faithfully predicts how trained attention-based networks propagate information; the paper supports this link only by visual comparison on three synthetic tasks, so if trained attention's effective diffusion diverges from $\\Delta$, the FS graph's design rationale would lose its foundation.","fun_headline_variants_meta":{"raw":{"variants":["Fidelity and mixing time define good feedforward graphs","FS graph: sparse recursive design matches full attention","Graph metrics predict feedforward network performance","New graph generator rivals full attention with fewer edges","Two complementary measures guide feedforward graph design"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1490,"prompt_tokens":956,"completion_tokens":534,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":465}},"tokens_in":572,"tokens_out":534,"duration_ms":5158,"temperature":1.0,"reasoning_tokens":465,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:25:21.409108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the paper's graph-attention architecture on a held-out battery of, say, fifty feedforward graph generators with matched in-degree budgets, measure averaged mixing time and normalized minimax fidelity for each, and regress out-of-distribution accuracy on the second-maximum and parity tasks against the two metrics; if the metric-ordering does not reproduce the empirical ranking, the claims that these measures capture graph quality are refuted. A sharper version would compute the same two quantities using the trained models' attention matrices instead of the uniform $\\Delta$, and check whether the ranking survives.","supporting_citations":[{"cited_title":"Speeding up random walk mixing by starting from a uniform vertex","cited_arxiv_id":null,"evidence_quote":"Supplies the averaged mixing time notion that the paper adopts as its first measure."},{"cited_title":"K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veli c kovi \\'c , P","cited_arxiv_id":null,"evidence_quote":"Shows over-squashing limits GNN power and that fully connected undirected graphs are not optimal for commute time, an analogy the paper uses against the feedforward star."},{"cited_title":"Discrete groups, expanding graphs and invariant measures, volume 125","cited_arxiv_id":null,"evidence_quote":"Provides the bipartite expander construction from random perfect matchings used for the FS graph's inter-block connections."},{"cited_title":"Some applications of modular forms, volume 99","cited_arxiv_id":null,"evidence_quote":"Provides the companion explicit expander construction used to turn inter-block chunks into sparse bipartite expanders."}],"review_version":1}