{"id":"84e49653-6212-45c7-b63f-5d3f8376eea2","arxiv_id":"2506.12220","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A large transformer with input length N can be simulated by O((N/M)^2) calls to a transformer of input length M, and O(N/M) calls suffice under average-case, sliding-window, or attention-sink assumptions.","lead":"This paper proves that a transformer handling long inputs can be replaced by many calls to smaller transformers that only handle short inputs, needing a quadratic number of calls in the worst case and a linear number in common settings. The result gives theoretical backing to hierarchical and windowed transformer designs and to using hardware optimized for short sequences.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central theorem assumes oracle MLPs can exactly invert softmax normalization and implement arbitrary lookups; if these are standard bounded ReLU MLPs of size O(d^2), the construction is not justified, so the advertised 'small transformer' is a strong oracle rather than the practical model.","rationale":"The reader's weakest assumption identifies the same load-bearing issue: the oracle's MLPs are assumed to perform arbitrary arithmetic and lookup-table operations. My stress-test sharpens this for the central worst-case theorem, where even the non-causal simulation requires exact algebraic inversion of the softmax ratio inside the oracle MLP. This is not a minor technicality: it is the mechanism by which unnormalized attention sums are recovered, and it is used in every oracle call of Step 1 of Lemma B.1. The paper states this assumption explicitly, so it is internally consistent; however, it substantially weakens the practical interpretation that 'small transformers' (as implemented with standard ReLU MLPs) can simulate large ones. The reader's CONDITIONAL verdict is appropriate: the proof is valid under the stated powerful-MLP model, but the model should be stated more prominently, and the realizability of the required arithmetic within O(d^2) resource bounds should be justified. I do not see a fatal flaw in the asymptotic construction itself; the off-by-one issue of adding a synthetic token to an input of length M is fixable by using blocks of size M-1 and does not change the O((N/M)^2) bound. The average-case and sliding-window results have additional proof gaps already noted by the reader, but those do not affect the main worst-case theorem. Therefore, no change to the reader's verdict is needed; the concern reinforces the conditional nature of the acceptance.","tokens_in":23774,"tokens_out":23662,"duration_ms":290537,"concrete_test":"Repair and re-derive Lemma B.1 with the oracle MLP restricted to a two-layer ReLU network of width O(d^2) and O(log N)-bit weights. Concretely, for M = d = Theta(log N) and epsilon = 1/(2N), compute the worst-case relative error in recovering A_{i,t} from the softmax ratio over all inputs satisfying the paper's bounds. If the error exceeds epsilon, or if an analytic lower bound shows that f(x) = x/(1-x) cannot be approximated to precision 1/N by any O(d^2)-parameter ReLU network of constant depth, then the central theorem does not apply to standard small transformers as advertised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.4 rests on Lemma B.1, where the oracle MLP must recover the unnormalized attention sum A_{i,t} from the softmax ratio A_{i,t}/(A_{i,t}+exp(0)) by computing exp(0) * r / (1-r). This is exact division and inversion of a nonlinear function. The paper's model allows MLPs to perform arbitrary basic arithmetic in O(d^2) time, but a standard transformer MLP is a fixed ReLU network of bounded size. With d = O(log N) and error tolerance epsilon = Theta(1/(2N)), an O(d^2)-parameter ReLU network is not shown to implement x/(1-x) to the required precision on the relevant domain [1/(C+1), C/(C+1)]. The same reliance appears in Lemma 3.3, where a single shared layer MLP must apply different instance-specific MLPs block-diagonally and pass other blocks through unchanged; this is only possible if the MLP is an arbitrary function of the full embedding, not a standard small network. Lemma A.3, imported from [SHT24], additionally requires an arbitrary lookup table, which cannot be encoded with O(d^2) parameters for arbitrary indexing functions tau. These are explicit model assumptions, but they are load-bearing: without them, the block-decomposition simulation of Theorem 3.4 does not go through. The paper does not prove these MLP capabilities are realizable within the stated O(d^2) resource bound, so the central claim is only established for a very powerful oracle model.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies simulating a large transformer with input length N by repeatedly invoking a small transformer oracle with input length M << N. The main result (Theorem 3.4) states that any transformer with L layers and H heads per layer can be simulated with O((N/M)^2 * HL/(H'L')) calls to an oracle with L' layers, H' heads, input length M, and embedding dimension O(dH'L'/H), with a matching worst-case lower bound. The paper also gives a linear number of calls under boundedness assumptions on attention weights (Theorem 4.1), and for sliding-window and attention-sink masking (Theorem 5.1). The proofs decompose the N x N attention matrix into M x M blocks, use synthetic tokens to recover normalization constants from softmax outputs, and pack independent single-layer, single-head instances into a multi-layer, multi-head oracle.","tokens_in":24066,"tokens_out":20376,"duration_ms":254964,"significance":"If the results hold in a realistic model, they provide a new decomposition of long-context transformer computation into short-context calls, with potential wall-clock speedups on hardware optimized for small contexts, and a theoretical justification for hierarchical chunking schemes. The paper's strengths include an explicit block-decomposition construction, a tight worst-case oracle-call count, parameter reuse with only constant-factor parameter blowup, and extensions to causal masking, sliding windows, and attention sinks. The main caveat is that the small transformer is an oracle whose MLPs are assumed to perform arbitrary arithmetic and lookup operations; this is a strong modeling assumption that should be stated prominently.","major_comments":[{"comment":"The simulation results are proved in an oracle model in which layer MLPs can perform arbitrary arithmetic operations (including exact division and inversion of the softmax ratio) and arbitrary lookup tables (Lemma A.3, imported from [SHT24]). These capabilities are load-bearing: Lemma B.1 recovers A_{i,t} from r = A_{i,t}/(A_{i,t}+1) by computing r/(1-r), and Theorem 4.1 uses Lemma A.3 to permute tokens. The paper does not show that these operations are realizable by a standard transformer MLP of size O(d^2), and with d=O(log N) and target error Theta(1/(2N)) in the approximate theorems, a universal-approximation invocation would require a precision analysis. The abstract and introduction present the result as simulation by 'transformers'; this should be qualified, or the realizability question should be addressed, because without these MLP powers the central construction does not go through.","section":"Section 2.1 and Lemma B.1"},{"comment":"The proof that one L'-layer, H'-head oracle can simulate H'L' independent single-layer single-head transformers relies on the claim that 'the other parts are passed through the layer without being changed.' Under the paper's Definition 2.2 there is no residual connection: the layer MLP receives only the concatenated attention outputs, and an attention output is a softmax-weighted sum of value vectors. A weighted sum cannot in general reproduce the untouched input blocks, so the induction over L' layers is not justified. The proof must either add residual connections to the transformer model and re-derive the construction, or give an explicit attention-based identity-passing mechanism (for example, using Lemma A.3) that works for all rows with the same attention weights that also compute the desired instance.","section":"Lemma 3.3 / Appendix B.3"},{"comment":"Several constructions feed the oracle a sequence of length M+1 while the oracle is specified to accept input length at most M. In Step 1 of Lemma B.1 the input is X[S_t,:] together with one synthetic token; in the cross-block case the input is the horizontal concatenation [X[S_t,:], X[S_{t'},:]] plus a synthetic row, also M+1 rows. Claim B.6 has the same structure. This is a constant-factor issue and can likely be repaired by reserving one slot and processing M-1 real tokens per call, but the theorem statements and the call-count bounds need to be adjusted accordingly.","section":"Lemma B.1 and Claim B.6"},{"comment":"The final step of Lemma B.1 states that computing the weighted sum Sum_t (B_{i,t}/A_{i,t}) * A_{i,t} / Sum_t A_{i,t} 'can be done either trivially or with O((N/M)^2) oracle calls with Lemma A.2,' but the allowed outside-oracle operations are only padding and concatenation, not multiplication or division. No concrete sequence of oracle calls is given that arranges the per-block values into inputs of length at most M and aggregates them per query. Please specify this aggregation subroutine; as written, the proof of Theorem 3.4 is incomplete at this step.","section":"Lemma B.1, final aggregation step"}],"minor_comments":[{"comment":"The 'average-case' assumption is deterministic boundedness of all attention weights (1/C <= a_{i,j} <= C and a mean-dominance condition), not a distributional average-case model; the terminology could mislead readers.","section":"Theorem 4.1"},{"comment":"In the proof of Lemma B.1, S_t is defined as {(t-1)M, ..., tM}, whereas the notation section defines S_t = {(t-1)M+1, ..., tM}; the off-by-one should be fixed.","section":"Lemma B.1"},{"comment":"The displayed formula appears to have a typo: the denominator should be Sum_{j=1}^{i-1} a_{i-1,j} + exp(0), not Sum_{j=1}^{i} a_{i-1,j} + exp(0).","section":"Claim B.6"},{"comment":"The statement says the transformer computes a 1 x d sum, but the transformer output is N x d; the statement should say that every output row equals the sum.","section":"Lemma A.2"},{"comment":"The lower-bound discussion uses T both for the number of oracle calls and for the large transformer; please use distinct notation to avoid confusion.","section":"Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely question and the block-decomposition idea is appealing. My main concern is that the central theorem depends on an oracle model with very strong MLPs and on a pass-through claim that is not justified without residual connections. These are fixable, but the revision should either add residual connections to the model (standard in practice) or provide a complete proof of Lemma 3.3. I would also ask the authors to state the MLP assumption prominently, since the current phrasing overclaims relative to the formal model."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Josh, this one is worth your time. The paper introduces a new oracle model where you simulate a length-N transformer by making calls to a transformer that only takes length M, and proves two kinds of results. The headline is O((N/M)^2) calls suffice for any transformer, and that quadratic dependence is tight, following from the known attention lower bound. The block-decomposition construction in Lemma 3.1 is explicit: split the attention matrix into M-by-M blocks, use a synthetic token to recover the softmax denominator, and then combine. I checked the algebra; it works. The multi-head/multi-layer extension via Lemma 3.3 is also sound: pack H'L' independent single-head instances into one oracle's heads and layers using block-diagonal weights. This is the first provable expressivity guarantee for hierarchical transformer-style chunking, which is a real contribution.\n\nThe linear-call results for average-case inputs, sliding windows, and attention sinks are plausible but unevenly written. The aggregation step in the worst-case proof is dismissed as trivial when it needs a short argument. The sliding-window proof says later chunks follow identically without showing it. The concentration step in Theorem 4.1 uses sampling without replacement as if it were iid; that's fixable with standard Hoeffding for sampling without replacement, but it has to be written down. None of this looks fatal, but the paper needs a careful revision before I'd trust the linear bounds as stated.\n\nOn the complaint that the oracle MLP is too strong: that's partially fair but not a hidden flaw. The paper explicitly assumes oracle MLPs can do arbitrary arithmetic in O(d^2) time and can implement lookup tables. That is a strong assumption — a vanilla ReLU MLP with O(d^2) parameters is not shown to compute x/(1-x) to the claimed precision, and the imported lookup-table lemma needs arbitrary indexing functions. If you read the paper as a statement about practical hardware, the simulation may not go through. But in the representational-strength literature, this is the standard way to model MLPs, and the authors say so. They should be more upfront about how strong the oracle is, and say whether the O(d^2) parameter budget is actually enough for the required functions. That's a clarity issue, not a reason to reject.\n\nCitations are fine. The one self-citation is to a published lower bound used only for the remark, not to define the target. The free parameter B in Theorem 4.2 is explicit.\n\nWho is this for? People working on transformer expressivity, hierarchical models, or long-context inference theory. It deserves a serious referee. Send it out, but expect revisions to tighten the appendix and the oracle assumptions.","headline":"A genuinely new oracle model for decomposing long-context transformers into small-transformer calls; the worst-case quadratic bound is solid, the linear-case results have fixable proof gaps, and the MLP assumptions are explicit but strong.","tokens_in":24604,"tokens_out":2880,"would_cite":true,"duration_ms":34878,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that any transformer that reads a long input of length N can be simulated by a small transformer that only reads short inputs of length M, using O((N/M)^2) oracle calls in the worst case and O(N/M) under average-case or…","keywords":["transformer simulation","self-attention","long context","oracle complexity","representational strength","sliding window attention","attention sinks","lower bounds"],"falsifier":"Run the normalization-recovery step of the main construction with a small transformer whose MLPs are fixed bounded-size ReLU networks instead of arbitrary functions, and test whether those networks can solve for $A_{i,t}$ from the output ratio $A_{i,t}/(A_{i,t}+1)$ and can perform the token reorderings required by the lookup-table lemma; if either fails, the claimed oracle calls will not produce the correct block sums.","tokens_in":23538,"feed_emoji":"🧩","tokens_out":10890,"duration_ms":121385,"temperature":0.7,"pith_summary":"This paper tries to establish that long-context transformer computation can be decomposed into many short-context transformer computations without sacrificing expressive power. The main theorem states that any transformer with input length $N$, $L$ layers, $H$ heads per layer, and embedding dimension $d$ is simulated by $O((N/M)^2 \\cdot HL/(H'L'))$ calls to a transformer oracle that accepts only length-$M$ inputs, with embedding dimension $O(dH'L'/H)$; the oracle parameters are mostly shared with the original transformer, so the total parameter count grows by only a constant factor. The worst-case quadratic call count is shown to be necessary. When attention coefficients are bounded, or when attention uses sliding windows or attention sinks, the paper proves that the linear $O(N/M)$ number of calls suffices. If correct, the results mean long-context workloads could be run on hardware tuned for short sequences, with only a constant parameter overhead.","feed_headline":"Long-context transformers reduce to short-context oracle calls","feed_subtitle":"Worst case needs O((N/M)^2) length-M calls; sliding-window, attention-sink and average-case inputs need only O(N/M).","key_machinery":"The load-bearing objects are the block decomposition of the attention matrix and a normalization-recovery trick. For each length-$M$ query interval and each length-$M$ key interval, the algorithm constructs an oracle input whose softmax output encodes the unnormalized block sum $A_{i,t}$ through the ratio $A_{i,t}/(A_{i,t}+1)$; a synthetic token supplies the known $+1$. A second lemma packs $H'L'$ independent single-head, single-layer transformers into one oracle by giving each layer its own coordinate block and choosing attention weights that leave the other blocks unchanged. A third ingredient is a lookup-table lemma that lets oracle calls reorder or index tokens, which is what powers the random-permutation estimator for average-case inputs and the causal-masking constructions.","core_discovery":"The central discovery is that the only serious obstacle to splitting a long attention computation into short blocks is the global normalization in softmax, and that obstacle can be removed by adding one synthetic token to the oracle input. The algorithm partitions the $N \\times N$ attention matrix into blocks of size $M \\times M$, one block per pair of query and key intervals. For each block, the oracle is fed a constructed sequence that includes a synthetic token with a known exponential score, so the output equals $A_{i,t}/(A_{i,t}+1)$; because the oracle's MLP is allowed to do division, the algorithm solves for the unnormalized sum $A_{i,t}$. Summing block contributions recovers the full softmax numerator and denominator, and the same construction is reused across all heads and layers by packing $H'L'$ independent single-head computations into one multi-layer, multi-head oracle. The parameters fed to the oracle mostly coincide with the original transformer's matrices, leaving only a constant factor blowup in the total number of parameters.","pith_inferences":["A testable extension is to check whether trained hierarchical or chunked transformers satisfy the bounded attention-coefficient condition; if they do, the linear-call theorem predicts that chunkwise simulation should be accurate.","An empirical question the paper leaves open is whether the per-call overhead and matrix-assembly steps in the quadratic simulation are small enough on real hardware to beat direct long-context attention.","The oracle MLP assumption, which includes arbitrary division and lookup tables, is the strongest point of contact with practice; a natural next step is to determine which constructions survive when oracle MLPs are restricted to fixed-size ReLU networks.","Because oracle calls share most query, key, and value entries, the simulation maps naturally onto a distributed or parallel setting with one device per block and only $O(L)$ rounds of synchronization."],"forward_implications":["If the simulation is correct, long-context transformer inference becomes a sequence of short-context oracle calls, so accelerators optimized for lengths around $M$ could be used for much longer inputs.","When a short-context oracle runs in $O(M)$ wall-clock time rather than $O(M^2)$, the total wall-clock time of the quadratic simulation is $O(N^2/M)$.","The worst-case quadratic lower bound means a general simulation with fewer calls would contradict known hardness for approximating attention, so no uniformly cheaper decomposition exists.","Under bounded attention coefficients, $O(N/M)$ oracle calls give a $(1+\\epsilon)$-approximation with high probability, providing a formal expressivity justification for chunked or hierarchical transformer-style processing.","Sliding-window attention and attention-sink masked transformers are simulatable with only $O(N/M)$ calls even for worst-case inputs, so these masked models are especially compatible with short-context execution."],"supporting_citations":[{"why":"Defines the transformer architecture and attention mechanism that the large transformer being simulated is built from.","marker":"[VSP+17]"},{"why":"Supplies the hardness result for approximating attention that makes the worst-case quadratic oracle-call lower bound tight.","marker":"[AS24]"},{"why":"Provides the lookup-table lemma and the strong-MLP assumption that let oracle calls reorder tokens and compute arithmetic inside the small transformer.","marker":"[SHT24]"},{"why":"Justifies treating MLPs as arbitrary continuous functions on compact domains, which the construction relies on for division and exponentiation.","marker":"[HSW89]"},{"why":"Introduces attention-sink masking, the model class that the linear-call simulation in Theorem 5.1 covers.","marker":"[XTC+24]"}],"fun_headline_variants":["Small transformers simulate large ones","Simulate long-context transformers with short-context","Worst case needs quadratic small models, average linear","Attention sinks and sliding windows reduce simulation cost","Split attention blocks, use small transformers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the small transformer's MLP layers can perform arbitrary arithmetic such as division and exponentiation and can implement arbitrary token-indexing lookup tables; if real MLPs are weaker than that, the block-decomposition simulation does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Small transformers simulate large ones","Simulate long-context transformers with short-context","Worst case needs quadratic small models, average linear","Attention sinks and sliding windows reduce simulation cost","Split attention blocks, use small transformers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002248,"raw_usage":{"total_tokens":8681,"prompt_tokens":927,"completion_tokens":7754,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":7688}},"tokens_in":543,"tokens_out":7754,"duration_ms":70072,"temperature":1.0,"reasoning_tokens":7688,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:58:25.980474+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the normalization-recovery step of the main construction with a small transformer whose MLPs are fixed bounded-size ReLU networks instead of arbitrary functions, and test whether those networks can solve for $A_{i,t}$ from the output ratio $A_{i,t}/(A_{i,t}+1)$ and can perform the token reorderings required by the lookup-table lemma; if either fails, the claimed oracle calls will not produce the correct block sums.","supporting_citations":[],"review_version":1}