acceptodds
Under review as a conference paper at ICLR 2027

Read Depth and Broadcast Depth: What Sharing Keys and Values Across Layers Costs a Transformer

Abstract

Language models increasingly share keys and values across layers, so many layers query caches that few layers compute. We separate the two roles of attention: the read depth ρ counts layers that query, or select from, the whole context afresh, and the broadcast depth β counts the key–value generations that global attention reads, each computed below its readers. Sharing preserves the first and not the second. The composition construction of Chen, Peng and Wu (FOCS 2025) works with one generation, and reusing or re-ranking selections within a generation adds no read depth: for a fixed architecture at logarithmic precision, read depth ρ cannot compose ρ functions on long enough prompts whose blocks lie beyond the sliding windows' reach. With one generation of per-token keys and selections and the windows below it, the hierarchy holds at linear length: following ρ+1 pointers between two m-entry tables farther apart than the windows' reach needs read bandwidth (the bits one side of the prompt sends over all reads) Ω(m) − O(ρ log m), less one hidden state, at read depth ρ, but O(ρ log n) at read depth ρ+1. Without sliding windows, layers reading one such generation need read bandwidth N/2 − log₂(1/(2ε)) to compute the inner product of two N-bit blocks with advantage ε over uniform inputs, whereas two generations compute it with two layers of logarithmic size. In these terms YOCO with a sliding-window self-decoder has broadcast depth 1 and read depth L/2, its sparse variant YOIO has read depth 1, and DeepSeek-V4.1-Flash, as specified, has broadcast and read depth 4 among 38 global layers; at published widths and p = 16 the bounds for YOCO's joins and YOIO's two-pointer chasing apply from prompts of order 10^7 tokens, but DeepSeek-V4.1-Flash's composition bound needs over 10^100000 tokens. Bounds concern one forward pass in p-bit arithmetic with exact attention partial sums, p possibly growing with the prompt length n.

Primary area:
learning theory
Keywords:
transformer expressivity, KV cache, cross-layer KV sharing, sparse attention, communication complexity, depth lower bounds

Reviews

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

This work proposes a new perspective on the depth of transformer architectures in the context of sharing keys and values across layers. The authors introduce the concepts of "read depth" and "broadcast depth" and show that the read depth survives KV sharing while the broadcast depth does not. They also analyze the theoretical lower bounds of the length of the hard prompts that a model would fail.

Critical strengths
  1. The authors discuss the theoretical expressiveness of transformers with KV sharing, which is a critical aspect of understanding the limitations and capabilities of modern transformer architectures.
  2. The analysis and proofs are sound and well-structured. The authors provide a clear theoretical framework that builds on the communication complexity of transformers and give a rough estimate of the lower bounds of the length of hard prompts that a model would fail.
Critical weaknesses

Disclaimer: I am not an expert in this area, and my comments are only an educated guess based on my understanding of the paper.

  1. The paper is well-written and the results are theoretically meaningful. However, the theoretical results are too loose to be informative, either for model design or for understanding the limitations of transformers. A prompt with 7M tokens is not a practical scenario currently for any models.
  2. The paper discusses the impact of "read depth" and "broadcast depth" on the expressiveness of transformers. In the context of KV sharing, the place where the keys and values are shared across layers is more crucial than their counts. For example, if we make DeepSeek-V4.1-Flash have the first 4-8 layers with full attention and the rest either reuse, reindex or use sliding window attention, the model is expected to perform much worse than the standard one. While in the paper these two models are considered almost equivalent, as they have the same read depth and broadcast depth. I understand this is perhaps beyond the scope of the paper, but missing this point keeps the hypothesis of the paper away from the practical reality of transformer architectures.
Questions for authors

See the weaknesses section.

1 comment
AuthorsOpenReview ↗

Response to Reviewer zk4P

Thank you for the review. Prompts of this length are beyond deployed contexts. What the results establish is a growth statement: for joins, one shared KV generation needs read bandwidth that grows linearly with the length, while two generations need two layers of logarithmic size at every length. The 7.6M figure is where that growth overtakes the bandwidth of one published model.

W1 (looseness and the 7M-token prompt).

the theoretical results are too loose to be informative

What the number measures. For the YOCO baseline (32 layers, 20 heads of dimension 128, p=16p=16), the join bound applies to every NN of at least 7,603,697, i.e. to prompts of about 1.52⋅1071.52\cdot 10^{7} tokens. At p=133p=133, which represents every BF16 value, it applies from N≥4.65⋅107N\ge 4.65\cdot 10^{7} (Section 5, Appendix G.2). The figure is a simplified upper bound, L2(w−1)+L⋅Bdense\frac{L}{2}(w-1)+L\cdot B_{\rm dense}, on the bits exchanged across the cut between the two blocks in our simulation of the 16 cross-decoder reads. The simulation's own count is smaller and already rules out every NN of at least 5,116,657. How close a model of this width can come to the bound is not known; the bound concerns one-generation models (YOCO, YOIO), not DeepSeek-V4.1-Flash, which has four generations.

How sharp the bounds are.

One KV generationLower boundConstruction
inner product of two NN-bit blocks, no sliding windowsread bandwidth N/2N/2 (Theorem 4.1(c))read bandwidth O(N+log⁡n)O(N+\log n) with ⌈N/b⌉\lceil N/b\rceil dense layers (Proposition F.4)
ρ+1\rho+1 pointers between two mm-entry tables, windows below the generation, tables beyond their reachread bandwidth Ω(m)−O(ρlog⁡m)\Omega(m)-O(\rho\log m), less one hidden state, at read depth ρ\rho (Theorem 3.3, Lemma 3.4)read depth ρ+1\rho+1, logarithmic size (Theorem 3.3(b))

The first row is tight in read bandwidth up to a constant factor. The second is tight in read depth.

What it implies for design.

  1. Joins need a second generation or linear read bandwidth. Two KV generations compute the inner product at every length with two dense layers of logarithmic size (Theorem 4.2). One generation without sliding windows needs read bandwidth at least N/2N/2 (Theorem 4.1(c)), so a model of logarithmic size needs Ω(N/log⁡n)\Omega(N/\log n) fresh-read layers, and ⌈N/b⌉\lceil N/b\rceil dense layers suffice (Proposition F.4).
  2. Reuse within a generation adds no reads for composition. For function composition, whose steps depend on a query that only the last position holds, reuse and re-selection layers within a KV generation add no read depth. At logarithmic precision and on long enough prompts, read depth ρ\rho cannot compose ρ\rho functions (Theorem 3.2). This is why only 4 of the 38 global layers of DeepSeek-V4.1-Flash count as reads.

Below the thresholds our results neither predict nor exclude a capability gap. We have added this to Section 5 of the revised PDF (paragraph "What the ledger says for design", in blue), together with where the thresholds come from.

W2 (where sharing happens).

the place where the keys and values are shared across layers is more crucial than their counts

We agree that the ledger invites the reading that equal depths mean equal models, and that placement can matter a great deal for a trained model. The depths are necessary conditions, not a ranking. Too little read depth forces failure on composition and pointer chasing at the stated lengths, and a single KV generation forces read bandwidth linear in NN for joins. Neither statement orders models with enough of both.

Take kk Full layers at the bottom (4≤k≤84\le k\le 8), with the remaining global layers reusing or re-selecting within the candidate pool. That variant has broadcast and read depth kk, at least the released model's 4, so our bounds give it no disadvantage. They neither predict nor exclude the performance difference you describe. The reason is a modelling choice, made as in Chen et al. (2025): token-wise maps are arbitrary functions, so the finite capacity of the layers between and after the reads is outside the model. For models with several KV generations, such as both models in your example, our bounds do not depend on where the fresh reads sit. For one-generation models, placement enters only through the layer σ0\sigma_0 that computes the shared cache and, with sliding windows, through the window-cone sizes, both in (4.1).

We have added a sentence on placement to Section 5 that states this scope.

If these clarifications address your concerns, we would appreciate it if you would reconsider your rating.

Reviewer_EnxNOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This is a strongly theory-oriented paper. The paper argues that, once KV caches are shared across different layers of a large model, the model’s capabilities can no longer be measured by the conventional notion of depth alone. Instead, depth should be decomposed into two metrics: read depth and broadcast depth, which represent, respectively, how many layers perform fresh reads over the full context and how many generations of KV representations are produced and made available for reading by subsequent layers. The paper primarily relies on a series of theorems to establish its conclusions and also discusses the boundaries of those conclusions. However, it does not deploy or evaluate the model on real hardware, so its engineering significance remains limited.

Critical strengths

The paper offers a relatively novel perspective by recognizing that sharing KV caches across layers affects different types of computational capabilities in different ways. The theoretical framework is also fairly comprehensive and provides useful directions for future work.

Critical weaknesses

The abstract lists a large number of theorems and numerical results but does not provide a concise summary of the paper’s central message, which reduces its readability. The paper does not evaluate the proposed analysis on real hardware, and its assumptions are highly idealized, making it difficult to establish the practical impact on real-world systems. In addition, the paper provides few visual summaries or simple examples to explain the overall theoretical framework.

Questions for authors
  1. What practical guidance does the theory proposed in this paper provide for deploying real-world models?

  2. Can the proposed theoretical framework be extended to more than two generations of KV representations?

3 comments
AuthorsOpenReview ↗

Response to Reviewer EnxN (1/2)

Response to Reviewer EnxN (1/2)

Thank you for the review. The central message, in two sentences: attention does two jobs, reading (a layer queries the whole context afresh) and broadcasting (a layer publishes new keys and values for later layers to read), and sharing keys and values across layers keeps the first and lowers the second. The two are different resources: a fresh read buys one step of a sequential lookup, while a further KV generation buys one level of aggregation that later layers can read, so the number of layers of a KV-sharing model hides two separate quantities. The revised abstract and introduction now state this right after the two definitions.

W1b (real hardware and idealized assumptions).

The paper does not evaluate the proposed analysis on real hardware, and its assumptions are highly idealized

The results are impossibility statements of the form "no choice of weights computes task X at length nn", each paired with a construction. A trained model run on hardware shows what training found, not what every choice of weights can do, so its failure would not confirm these bounds, and at deployable lengths, which lie below the thresholds in Section 5, its success would not contradict them. The constructions of Appendix F (for Theorem 3.1, its retrieval head) were executed in exact arithmetic at small sizes (on all inputs for most of them, on random instances for Propositions F.5(b) and F.6), with no errors (Appendix H).

For lower bounds, two idealizations are generous to the model: token-wise maps are arbitrary functions (any MLP of any size), and the precision pp may grow with the prompt length. The exact-sum rule is different: it is not a relaxation of real kernels. Proposition A.1, which we have added to Appendix A, states which results need it:

  • the bounds for sparse architectures (DeepSeek-V4.1-Flash, YOIO) need no exact sums: they hold for any deterministic kernel that evaluates each head from its selected entries, whatever its summation order, rounding or running maximum;
  • the two-party bounds for dense reads (Theorem 4.1 and the YOCO join bound) hold for dense heads that are not joint heads and scan the keys in increasing position order with a bounded running state, which covers rounded accumulation and online softmax with a running maximum as in Algorithm 1 of FlashAttention, with the running state in place of the exact partial sums;
  • for dense reads under such kernels, the pointer-chasing hierarchy (Theorem 3.3) holds in the weaker form "ρ\rho reads versus 2ρ+12\rho+1 pointers";
  • the composition bound for models with dense global layers (Theorem 3.2) keeps the exact-sum rule, as does the simulation of Chen et al. (2025, Lemma 3.1) that it builds on.

The per-architecture modelling assumptions stay as stated with each corollary in Appendix G (for DeepSeek-V4.1-Flash: one cold prefill, per-token expert routing, the tie rule, one precision, idealized tokens).

W1a (abstract). We have revised the abstract: right after the two definitions it now states the message above, and the sentence with the numerical thresholds has left the abstract (the numbers remain in Section 5). The definition paragraph of the introduction ends with the same sentence. The abstract field on OpenReview now matches the revised PDF.

W1c (visual summaries and simple examples). We have added Figure 2 to Section 2, with two worked examples. A two-step lookup is answered by two reads of one shared cache. A join needs a second generation or read bandwidth linear in the block length; with a second generation, in layer 1 each position N+iN+i fetches xix_i and stores ui=xiyiu_i=x_iy_i, and layer 2, reading the new generation, averages the uiu_i (Theorem 4.2). Figure 1 (the layer map of DeepSeek-V4.1-Flash) and Table 1 (the depths of five architectures) remain the visual summaries of the ledger.

AuthorsOpenReview ↗

Response to Reviewer EnxN (2/2)

Response to Reviewer EnxN (2/2)

Q1 (practical guidance). Three statements follow directly from the theorems:

  1. Composition needs fresh reads, and reuse within a generation adds none. For function composition, whose steps depend on a query that only the last position holds, reusing or re-ranking a selection within a KV generation saves compute but adds no read depth: at logarithmic precision and on long enough prompts, read depth ρ\rho cannot compose ρ\rho functions (Theorem 3.2). So in DeepSeek-V4.1-Flash 4 of the 38 global layers count (Figure 1). Reusing a selection across generations, as in IndexCache, can add read depth (Proposition F.2).
  2. A join needs a second KV generation or read bandwidth linear in its size. With one generation, as in YOCO, joining two NN-bit blocks needs read bandwidth linear in NN (Theorem 4.1); one more generation, computed after a global read, does it with two layers of logarithmic size (Theorem 4.2).
  3. Where the one-generation limit sits. For YOCO with a sliding-window self-decoder, joins become impossible, whatever the weights, once NN exceeds about L⋅BdenseL\cdot B_{\rm dense} bits plus a boundary term (Corollary G.2), which grows with read depth, heads, head dimension and precision. At the published width and p=16p=16 this is every NN of at least 7,603,697. Below that length the theory makes no prediction.

We have added these three points to Section 5 (paragraph "What the ledger says for design").

Q2 (more than two generations). Partly. The definitions and Theorem 3.2 hold for any number of generations. Two generations let ρ\rho reads follow 2ρ−12\rho-1 pointers (Proposition F.3). For every β\beta, β\beta generations and (β−1)+2m(\beta-1)+2m dense reads compute the (β+1)(\beta+1)-level task, i.e. reads can replace one broadcast at a cost linear in the fan-in mm (Proposition F.6). The matching lower bound beyond β=1\beta=1 is Conjecture 4.3. Section 4 states the obstacle: first-generation reads can prepare hints that the second generation publishes, so a single two-party cut is too weak, and a proof must show that such hints are nearly uncorrelated with the level-two parities.

If these answers and the revisions address your concerns, we would appreciate it if you would reconsider your rating.

Thank you for your rebuttal, as well as for conducting the additional experiments. Your responses have satisfactorily addressed my concerns, and I have updated my review score accordingly.

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

This paper studies how sharing keys and values across layers affects the expressive power of Transformers. It separates read depth from broadcast depth and uses function composition, pointer chasing, and join-parity tasks to show that these are different computational resources. It also uses these measures to analyze existing KV-sharing architectures.

Critical strengths

1.The proofs and their boundary conditions are handled carefully. The authors state the arithmetic and architectural assumptions explicitly and account for sliding windows, candidate-pool re-selection, and index reuse. They also provide counterexamples showing when cross-generation reuse can overcome the stated limitations, making the scope of the results clearer.

2.I find the distinction between read depth and broadcast depth useful. It separates querying existing information from making intermediate results available to later layers. This helps explain why sharing KV states and reusing selected indices have different effects, and offers a more informative view than counting layers alone.

Critical weaknesses

1.The implications for deployed models remain tied to the arithmetic convention in Definition 2.3. Scores and weights are rounded, but attention partial sums are accumulated exactly. As the authors explicitly note, the simulations do not directly cover rounded accumulation or running-max attention kernels. These assumptions are clearly stated, but whether the same separations hold under practical attention implementations remains open, which limits the direct architectural interpretation.

2.I find the practical implications of the architectural examples difficult to assess. For DeepSeek-V4.1-Flash, the hard instances obtained in Corollary G.1(v), at the stated widths and p = 16, exceed 10^100000 tokens. The authors acknowledge this limitation, and the YOCO/YOIO examples involve substantially smaller instances. Still, these results leave unclear when the identified depth differences would lead to capability differences at feasible context lengths.

3.The linear-length read-depth separation in Theorem 3.3 requires a single KV generation with per-token entries and no local mixing above the shared source. Theorem 3.2 covers multiple generations, but the exponent governing its hard-instance size grows exponentially with read depth. The broadcast-depth separation is established for one versus two generations, while the general hierarchy remains conjectural. These results leave a limited characterization of how the proposed depth measures constrain computation in more general architectures.

I would consider raising my score if the authors can satisfactorily address these concerns.

Questions for authors

Please see Weaknesses

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2ceN (1/2)

Response to Reviewer 2ceN (1/2)

Thank you for the careful review. The main point first: in the lower-bound proofs, the exact-sum convention of Definition 2.3 is needed only for dense global reads. The bounds for the sparse architectures (DeepSeek-V4.1-Flash, YOIO) hold for any deterministic kernel that evaluates each head from its selected entries. The two-party bounds for dense reads survive, for dense heads that are not joint heads, kernels that scan the keys in increasing position order with a bounded running state, which covers rounded accumulation and online softmax with a running maximum as in Algorithm 1 of FlashAttention. Under such kernels the pointer-chasing hierarchy holds in a weaker form, ρ\rho reads versus 2ρ+12\rho+1 pointers.

W1 (exact partial sums and real kernels).

whether the same separations hold under practical attention implementations remains open

We have added the following as Proposition A.1 in Appendix A of the revised PDF (in blue), with a sentence after Definition 2.3 pointing to it. The full proof, including the construction in item 3, is in Appendix A.

  1. Sparse layers need no exact sums. In every simulation (Lemmas B.2, D.1, E.1), a fresh selection is answered with local top-kk lists together with the KV-source states of the listed entries. Wherever the proofs combine partial sums of a sparse head (joint or not), the player doing so knows the reading position's state and every attended item, so it can evaluate the head directly. Hence, for models without dense global layers, the lower bounds of Theorem 3.2(a),(b), Theorem 3.3(a), Theorem 4.1, Corollary G.1 (all 38 global layers of DeepSeek-V4.1-Flash are selection, re-selection or reuse layers) and Corollary G.4 (YOIO) hold, with unchanged bandwidths, whenever each head's output is a deterministic function of the reading position's states, its selected entries (in selection order) and its window items. That covers any summation order (for instance by indexer score), any rounding and any running maximum. It does not cover nondeterministic kernels, kernels whose order depends on unselected entries, or kernels that couple different query positions.
  2. Dense reads under streaming kernels. Suppose a dense head that is not a joint head computes its output at position ii by scanning the keys in increasing position order, in tiles of at most TT positions, keeping a running state of SS bits. Sequential rounded accumulation in a bb-bit format has T=1T=1 and S=(d+1)bS=(d+1)b. Online softmax with a running maximum, as in Algorithm 1 of FlashAttention (Dao et al., 2022), has S=(d+2)bS=(d+2)b. At the cut, Alice sends her running state instead of her exact partial sums, and T−1T-1 extra boundary tokens let Bob finish the tile that straddles the cut. Theorem 4.1(a),(b) then hold with BdenseB_{\rm dense} replaced by HSHS and T−1T-1 added to the boundary term, and Theorem 4.1(c) with 2Bdense2B_{\rm dense} replaced by HS+2pHdHS+2pHd and T−1T-1 added to the left side. For YOCO with a sliding-window self-decoder, computing JPN\mathrm{JP}_N forces L2(w−1)+(T−1)+L2(2pHd+HS)≥N\tfrac{L}{2}(w-1)+(T-1)+\tfrac{L}{2}(2pHd+HS)\ge N. At the width of the YOCO baseline, with p=16p=16, tiles of T=128T=128 and a running state of d+2d+2 32-bit numbers per head, this rules out every NN of at least 2,650,224, i.e. prompts of 5,300,449 tokens or more.
  3. Pointer chasing is where exact sums matter. With dense reads evaluated by a scan, each read takes two messages: Alice's state, then the head output from Bob. The protocol behind Theorem 3.3 then has 2ρ2\rho alternating messages, so, with all global layers dense and the tables T−1T-1 blanks farther apart, read depth ρ\rho fails (2ρ+1)(2\rho+1)-step alternating pointer chasing unless its reads, together with one hidden state, carry Ω(m)−O(ρlog⁡m)\Omega(m)-O(\rho\log m) bits. This is exactly tight for general scans: a scan whose state holds the current pointer advances two pointers in one read, so ρ\rho such reads follow 2ρ2\rho pointers, and the "ρ\rho versus ρ+1\rho+1" form of Theorem 3.3 does not extend to arbitrary scanning kernels. Whether the specific arithmetic of rounded accumulation or online softmax can do this is open. For sparse reads, including YOIO, Theorem 3.3 holds unchanged (item 1).
  4. Not covered. Theorem 3.2 for models with dense global layers under streaming kernels. In the communication model of Chen et al. (2025) each responder answers once per epoch, whereas a position-order scan chains the responders within one read. That case keeps the exact-sum convention, as in Chen et al. (2025, Lemma 3.1).
AuthorsOpenReview ↗

Response to Reviewer 2ceN (2/2)

Response to Reviewer 2ceN (2/2)

W2 (feasible context lengths).

The 1010000010^{100000} figure is the instance size of the composition bound, Theorem 3.2, inherited from the instances of Chen et al. (2025), whose exponent grows like 8ρ8^{\rho}. We report it to calibrate that bound, not as a prediction. The bounds within one KV generation are linear and much shorter. At the published widths and p=16p=16, the YOCO baseline fails JPN\mathrm{JP}_N for every NN of at least 7,603,697 (prompts of about 1.52⋅1071.52\cdot 10^{7} tokens), and YOIO fails two-step pointer chasing on tables of 1.42⋅1071.42\cdot 10^{7} entries (prompts of about 2.83⋅1072.83\cdot 10^{7} tokens). Both hold for every choice of weights (Section 5).

These thresholds count bits. Up to the boundary term, the YOCO threshold is L⋅BdenseL\cdot B_{\rm dense}, a simplified upper bound on the bits exchanged across the cut in our simulation of the 16 cross-decoder reads. The simulation's own count is smaller and rules out every NN of at least 5,116,657 (the count behind the streaming figure in W1). So the threshold grows linearly with the read depth, the number of heads times the head dimension, and the precision. Without sliding windows, the join bound is matched up to a constant factor by a construction that also reads one generation, with ⌈N/b⌉\lceil N/b\rceil dense layers (Proposition F.4). The pointer-chasing bound is tight in read depth (Theorem 3.3(b)). Below the thresholds the theory makes no prediction: a capability gap at the context lengths deployed today is neither implied nor excluded. We have added this to Section 5 of the revised PDF (paragraph "What the ledger says for design", in blue).

W3 (more general architectures).

The three limits are accurate. The conditions of Theorems 3.2 and 3.3 are necessary for the statements as given, and the limit on the exponent of Theorem 3.2 also applies to standard transformers:

  • One generation in Theorem 3.3. With a second generation, ρ\rho dense reads of logarithmic size follow 2ρ−12\rho-1 pointers (Proposition F.3), so (ρ+1)(\rho+1)-step pointer chasing no longer separates read depth ρ\rho from ρ+1\rho+1 for ρ≥2\rho\ge2. The condition of no local mixing above the source is also needed: a window of m+1m+1 positions above the source would let the last position look up Bob's table without a global read. Theorem 3.2 needs the reuse to stay within a generation, since reuse across generations adds read depth (Proposition F.2).
  • The exponent of Theorem 3.2. Theorem 3.2 covers any number of generations and every layer type, and its exponent comes from the instances of Chen et al. (2025). A standard transformer is the typed model with β=ρ=L\beta=\rho=L, so a read hierarchy for many generations at polynomial length with an exponent independent of ρ\rho would in particular give one for standard transformers (open problem 2 in Appendix I).
  • Broadcast depth. One versus two generations is proved: Theorems 4.1 and 4.2, and Proposition F.5 for the first level of layered path parity. For every β\beta, reads can replace one broadcast at a cost linear in the fan-in (Proposition F.6). That every further level needs its own generation is Conjecture 4.3. Section 4 names the obstacle: first-generation reads can prepare hints that the second generation publishes, so a single cut is too weak.

We have added a sentence to the Discussion saying which conditions are necessary (Propositions F.2 and F.3).

If the kernel result and these clarifications address your concerns, we would appreciate it if you would reconsider your rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response (1/2)

General Response (1/2)

We thank the three reviewers. This comment summarizes the contribution, the answers to the concerns that more than one review raised, and the revisions. Changed text in the revised PDF is in blue.

The contribution in one paragraph. Many language models now share keys and values across layers (cross-layer attention, YOCO, YOIO, the Reuse layers of DeepSeek-V4.1-Flash), so the number of layers no longer measures what a model can compute. We split depth into read depth ρ\rho, the layers that query the whole context afresh, and broadcast depth β\beta, the distinct key-value generations that later layers read. Then:

  1. sharing keeps read depth: r+1r+1 fresh reads of one shared cache compose rr functions, and at logarithmic precision, on long enough prompts, read depth rr cannot, however many layers reuse or re-rank a selection within a generation (Theorems 3.1, 3.2); within one generation, with the windows below it, read depth ρ\rho and ρ+1\rho+1 are separated at linear length (Theorem 3.3);
  2. sharing lowers broadcast depth: with one generation, joining two NN-bit blocks needs read bandwidth linear in NN, whereas two generations do it with two layers of logarithmic size (Theorems 4.1, 4.2);
  3. a ledger reads these depths off published layer maps: YOCO has β=1\beta=1 and ρ=L/2\rho=L/2, YOIO has ρ=1\rho=1, DeepSeek-V4.1-Flash has β=ρ=4\beta=\rho=4 among 38 global layers.

The tools are communication lower bounds, the standard route to unconditional limits on transformers (Sanford et al., 2023; Peng et al., 2024; Chen et al., 2025). The reviews describe the proofs as handled carefully (Reviewer 2ceN), the read/broadcast distinction as useful (Reviewer 2ceN) and relatively novel (Reviewer EnxN), and the analysis as sound (Reviewer zk4P). No review identifies an incorrect proof step.

1. Real attention kernels (Reviewer 2ceN W1, Reviewer EnxN W1b). In the lower-bound proofs, the exact-sum convention of Definition 2.3 is needed only for dense global reads. We have added Proposition A.1 to Appendix A, with a sentence after Definition 2.3:

  • Sparse layers need no exact sums. Every simulation answers a fresh selection with top-kk lists and the listed entries' states, and every softmax over selected entries can be evaluated by a player who holds all its items. So the bounds for DeepSeek-V4.1-Flash (Corollary G.1) and YOIO (Corollary G.4) hold for any deterministic kernel that evaluates each head from its selected entries, whatever its summation order, rounding or running maximum.
  • Dense reads (heads that are not joint heads) under kernels that scan the keys in increasing position order with a bounded running state (rounded accumulation; online softmax with a running maximum, as in Algorithm 1 of FlashAttention) keep Theorem 4.1 and the YOCO join bound. The running state replaces the exact partial sums, and a boundary term covers the tile that straddles the cut.
  • Pointer chasing is where exact sums matter. With such kernels, Theorem 3.3 holds as "read depth ρ\rho versus 2ρ+12\rho+1 pointers", still linear in the table size, and this is exactly tight for general scans, which can advance two pointers per read. The composition bound with dense layers (Theorem 3.2) keeps the exact-sum convention.

2. What the thresholds mean (Reviewer 2ceN W2, Reviewer zk4P W1, Reviewer EnxN Q1, Reviewer zk4P W2). At published widths and p=16p=16, the bounds apply from prompts of about 1.52⋅1071.52\cdot 10^{7} tokens (YOCO joins, every NN of at least 7,603,697) and 2.83⋅1072.83\cdot 10^{7} tokens (YOIO, two-step pointer chasing), for every choice of weights. The 1010000010^{100000} figure belongs to the many-generation composition bound inherited from Chen et al. (2025). What the thresholds are:

  • the YOCO threshold is, up to a boundary term, L⋅BdenseL\cdot B_{\rm dense}, a simplified upper bound on the bits exchanged across a cut in our simulation of the reads, so it scales with read depth, heads, head dimension and precision;
  • without sliding windows the join bound is matched up to a constant factor by a one-generation construction with ⌈N/b⌉\lceil N/b\rceil dense layers (Proposition F.4), and the pointer-chasing bound is tight in read depth (Theorem 3.3(b));
  • a second KV generation removes the join barrier at every length (Theorem 4.2);
  • below the thresholds the theory makes no prediction.

The depths are necessary conditions for specific tasks, not a ranking of architectures. For models with several KV generations the bounds do not depend on where the fresh reads sit; for one-generation models, placement enters only through the layer that computes the shared cache and the window cones. We have added to Section 5 a short paragraph on what the ledger implies for design, on where the thresholds come from, and on placement.

AuthorsOpenReview ↗

General Response (2/2)

General Response (2/2)

3. Scope beyond one or two generations (Reviewer 2ceN W3, Reviewer EnxN Q2). Two conditions are necessary for the statements as given. With two generations, ρ\rho reads follow 2ρ−12\rho-1 pointers (Proposition F.3), and reuse across generations adds read depth (Proposition F.2). The composition bound holds for any number of generations, and Proposition F.6 gives the upper bound for every β\beta. Open, and stated as open in the submission (Conjecture 4.3; Appendix I): the broadcast hierarchy beyond β=1\beta=1, and a many-generation read hierarchy at moderate length, which would in particular give one for standard transformers.

4. Presentation (Reviewer EnxN W1a, Reviewer EnxN W1c). We have revised the abstract to state the central message right after the two definitions (a fresh read buys one step of a sequential lookup; a further KV generation buys one level of aggregation that later layers can read), and the numerical thresholds now appear only in Section 5. We have also added a main-text figure (Figure 2) with two worked examples: two reads of one cache follow a two-step lookup, and a join with a single generation needs read bandwidth linear in NN.

Revisions (in blue in the revised PDF).

ChangeWhereFor
Proposition A.1 (kernels) and a pointer after Definition 2.3Appendix A, Section 2Reviewer 2ceN W1, Reviewer EnxN W1b
Thresholds: origin and scope; design implications; placementSection 5Reviewer 2ceN W2, Reviewer zk4P W1, Reviewer EnxN Q1, Reviewer zk4P W2
Necessary conditions of Theorems 3.2 and 3.3Section 6Reviewer 2ceN W3, Reviewer EnxN Q2
Central message stated after the definitions; numbers moved to Section 5Abstract; Section 1Reviewer EnxN W1a
Worked-example figureSection 2, Figure 2Reviewer EnxN W1c

The main text ends on page 10, within the 10-page limit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.