{"id":"0af4dbe2-e56c-449d-877d-360a0b130f66","arxiv_id":"2505.04994","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A leave-one-out attention preprocessing scheme makes in-context learning permutation invariant without sacrificing access to other context examples, improving length and out-of-distribution generalization.","lead":"Large language models are sensitive to the order of examples in their prompt, even when the examples are independent. This paper proposes InvICL, a way to make in-context learning order-invariant while preserving information non-leakage and interaction between examples, and reports moderate gains on benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3.5's non-leakage characterization treats diagonal self-attention as non-leaky, but Definition 3.2 forbids any dependence on y_i; since a diagonal mask lets row i attend to h_i containing y_i, the formal derivation of InvICL from Propositions 3.4–3.6 is internally inconsistent.","rationale":"The paper's central contribution has two parts: an empirical claim that InvICL outperforms prior invariant and standard ICL methods, and a theoretical narrative that derives the architecture from three desiderata. The empirical part is credible: code is provided, results are reported with standard errors across three base models, and the OOD gains (e.g., 48.4 vs 43.6 average on unseen-domain target tasks) are larger than the in-distribution gains. I would not reject on empirical grounds alone. However, the theoretical narrative is load-bearing for the claim that the design is 'principled' rather than just another empirically good mask. The reader's identified inconsistency in Proposition 3.5 is real: Appendix D.3 explicitly permits self-loops while Definition 3.2 requires invariance of f_i to y_i, and under the paper's per-example graph a diagonal entry makes f_i depend on y_i. The same issue appears in Proposition 3.6, which endorses the diagonal BoE mask as non-leaky. Since the two-stage LOO design is introduced precisely to escape the limitations of the diagonal mask, the formal derivation should have excluded self-loops or redefined non-leakage at token granularity. A concrete Jacobian check would settle whether the actual InvICL implementation leaks; if it does not, the correct fix is to revise Propositions 3.5 and 3.6 and the surrounding text, not to reject the method. This is consistent with the reader's CONDITIONAL verdict, so I recommend no change.","tokens_in":23021,"tokens_out":9647,"duration_ms":95893,"concrete_test":"Build the n=1 and n=2 versions of the attention layer in Eq. (2) with H formed from (x_i, y_i) pairs. For the diagonal mask M1, numerically compute the Jacobian \\partial f_i / \\partial y_i: if it is nonzero, Proposition 3.5's 'lower triangular implies non-leakage' is false under Definition 3.2. Then compute the same Jacobian for the actual parallel LOO mask in Figure 2(d) on the duplicated input; if \\partial \\hat y_i / \\partial y_i = 0 for every context position, the shipped architecture is non-leaky and only the formal statements (Propositions 3.5-3.6 and the derivation in Section 3.2) need repair, e.g., by defining non-leakage on the token-level graph where the query token does not attend to its own label token.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing assumption is the equivalence in Proposition 3.5, used to conclude in Proposition 3.6 that permutation invariance plus non-leakage forces a diagonal (BoE) mask, which then motivates the two-stage leave-one-out design. The proof in Appendix D.3 states 'Since the original graph allows self-loop, which corresponds to the diagonal elements, the adjacency matrix is lower triangular,' i.e., it counts self-loops as non-leaky. But under Definition 3.2, f(..., x_i, y_i, ...)_i must be invariant to y_i. In the paper's per-example graph, node i represents \\tilde x_i = (x_i, y_i), so a diagonal attention entry lets row i aggregate h_i itself, which contains y_i; changing y_i changes h_i and therefore f_i. A minimal counterexample is n=1 with mask M=[0]: the mask is lower triangular, so Proposition 3.5 would certify non-leakage, yet f_1 depends on y_1 when the output head reads h_1 after self-attention. This is not merely a wording issue: it breaks the chain Propositions 3.4-3.6, so the claim that the LOO architecture is the unique principled way to combine invariance and non-leakage does not follow from the stated results. The implemented InvICL mask may still be genuinely non-leaky because the LOO stage excludes example i, and token-level AR attention can be non-leaky without excluding self-loops; the defect is in the formal abstraction, not necessarily in the released model.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that the poor performance of prior permutation-invariant ICL algorithms stems from violating two additional desiderata: information non-leakage (the prediction for a context example must not depend on its own label) and context interdependence (each example's encoding should depend on other examples). It formalizes these as Definitions 3.1-3.3, proves in Propositions 3.4-3.6 that a single attention mask satisfying invariance and non-leakage must be diagonal (BoE), and then augments BoE with a leave-one-out pre-encoding step to restore context interdependence. The resulting InvICL is implemented in parallel by duplicating the context sequence and using a two-stage mask. Experiments on synthetic linear regression, sparse linear regression, decision trees, OOD shifts, and MetaICL finetuning on 142 tasks with GPT-2/GPT-Neo/Pythia report faster convergence, better length extrapolation, and higher average accuracy than AR, Prefix, PCW, SAICL, BatchICL, and NoPE baselines. Appendix C gives a gradient-descent approximation theorem. Code is publicly released.","tokens_in":23369,"tokens_out":10331,"duration_ms":106274,"significance":"Conditional on the correctness of the theoretical derivation, the paper would make a solid contribution: it identifies two design axes that are intuitive but previously scattered, gives a clean practical recipe, and demonstrates that order invariance need not cost accuracy. The evaluation is unusually broad: three base models, seven MetaICL settings, OOD subsets, multiple synthetic function classes, ablations of the mask and positional encoding, and a sensitivity measure that confirms exact permutation invariance (0.00 in Table 4). The parallel implementation and released code address the main practical concern with leave-one-out schemes. The principal reservation is that the 'principled design' chain in Section 3.2 is not internally consistent as stated, so the contribution is better described as a well-engineered architecture with a plausible formal motivation, pending repair of the propositions.","major_comments":[{"comment":"The non-leakage characterization in Proposition 3.5 is inconsistent with Definition 3.2. The proof explicitly allows self-loops on the diagonal ('Since the original graph allows self-loop, which corresponds to the diagonal elements, the adjacency matrix is lower triangular'), but a diagonal attention entry at (i,i) lets row i aggregate h_i, which by construction contains y_i, so the prediction f_i depends on y_i. A minimal counterexample is n=1 with mask M=[0]: the mask is lower triangular, yet the output read from h_1 after self-attention changes when y_1 changes. Consequently Propositions 3.5 and 3.6 do not establish that a diagonal mask is the only invariant non-leaky single-layer choice, and the derivation of the leave-one-out design from these propositions does not follow. The implemented InvICL may still be non-leaky because the second-stage LOO attention excludes the example's own label embedding, but the stated formal equivalence needs repair, for example by requiring strictly lower triangular masks (no self-loops) and by specifying how residual connections are treated in the graph abstraction.","section":"Section 3.2, Proposition 3.5 and Appendix D.3"},{"comment":"The graph abstraction used in the propositions treats each context example as a single node with hidden state h_i = (x_i,y_i), whereas the implemented Algorithm 1 keeps h_x and h_y separate and updates h_y^{(k)} from other examples' embeddings. The propositions classify masks on the n-node joint graph, but the actual InvICL uses a duplicated sequence and a bipartite LOO attention pattern that is not among the single-layer masks {M1,M2,0} classified in Proposition 3.4. The paper should state explicitly that the two-stage design goes outside the single-layer mask classification and prove non-leakage and invariance for the two-stage mask directly. As written, the claim that InvICL is the unique principled combination of the three desiderata is not supported by the formal results.","section":"Section 3.2 and Algorithm 1"},{"comment":"The abstract and conclusion claim that InvICL 'surpasses' AR ICL in most benchmarks, but in the 'All target tasks' block several differences are within one standard deviation, for example HR→LR 45.1±1.31 versus 43.4±0.76, CLASS→CLASS 42.9±0.86 versus 43.4±1.36, and the average 42.4±0.87 versus 41.9±1.15. Only the 'Target tasks in unseen domains' block shows consistent and larger gains. Please provide significance tests or paired comparisons across seeds and temper the wording, or present the OOD setting as the primary empirical claim.","section":"Section 4.2, Table 2"}],"minor_comments":[{"comment":"Figure 4 and Figure 6(b) report length-generalization and decision-tree results without error bars; adding standard deviations over random seeds would make the claims easier to evaluate.","section":"Figure 4 and Figure 6"},{"comment":"The BatchICL baseline uses the 15-th layer for aggregation with no sensitivity analysis; please clarify whether this choice was fixed a priori or selected on the evaluation tasks.","section":"Appendix A.2"},{"comment":"There are several typos and formatting issues, including 'Desicion tree' in Figure 6, 'infty' in place of '-\\infty' in Appendix D.2, and the inconsistently typeset author reference 'V on Oswald' in the body and bibliography.","section":"General presentation"},{"comment":"The discussion counts the number of '0' entries in the mask and concludes InvICL has the same order as Prefix ICL and twice the cost of AR ICL, while Table 3 reports nearly identical wall-clock times; please reconcile the analytical count with the measured inference time and note any memory overhead beyond the reported 14%.","section":"Section 5, Theoretical Complexity"},{"comment":"Context interdependence is defined existentially, so any non-constant aggregation satisfies it; the paper should clarify whether this weak notion is intended or whether a stronger, quantitative notion (e.g., sensitivity to all other examples) is needed to support claims like 'maximizing context interdependence'.","section":"Definition 3.3"}],"recommendation":"major_revision","confidential_remarks":"The formal gap in Section 3.2 is the main risk: the self-loop issue in Proposition 3.5 directly undermines the claimed logical derivation of the LOO design, even though the released model may be non-leaky for other reasons. I would encourage a revision rather than rejection because the architecture and empirical evaluation are strong and the formal chain can likely be repaired by redefining the abstraction or by reproving the two-stage design directly. The code release and breadth of experiments are clear strengths."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: InvICL is a genuinely new and reasonably effective way to make ICL permutation-invariant without the usual accuracy drop. The two-stage Bag-of-Examples + leave-one-out pre-encoding, computed in one pass by duplicating the input, is a clever trick, and the empirical work is mostly solid. But the paper's formal scaffolding has a load-bearing hole that the authors need to fix or disclaim.\n\nWhat's actually new: the architecture. I don't know of prior work combining independent BoE encoding with LOO pre-encoding in a single duplicated sequence. The paper also gives a clean three-desiderata framing (invariance, non-leakage, interdependence) that's useful even if the formalization is imperfect. The synthetic experiments are well-designed: linear regression, sparse linear, decision trees, and OOD shifts. And on real-world MetaICL benchmarks, InvICL beats AR ICL on most OOD settings and is roughly at parity or slightly better on average. The code is public, which earns credit.\n\nThe soft spots, in proportion: first, the formal logic. Proposition 3.5 says non-leakage iff the attention mask can be made lower triangular, with self-loops allowed. But under Definition 3.2, the prediction for example i must not depend on y_i. In the paper's own graph abstraction, node i represents (x_i, y_i), so a diagonal attention entry feeds h_i back to itself, and h_i contains y_i. The n=1 counterexample is decisive: M=[0] is lower triangular, yet f_1 changes when y_1 changes. This invalidates the chain from Propositions 3.4-3.6, so the 'principled design' that forces the LOO scheme doesn't follow. The implemented InvICL mask may still be genuinely non-leaky because the LOO stage excludes example i; that's fine. But the uniqueness claim is not proven.\n\nSecond, the real-world gains over AR ICL are mostly small, within noise on several tasks. The large win on HR→LR OOD is real, but the all-task average is about half a point. Third, in the synthetic OOD experiments they drop Prefix and BoE baselines post hoc ('for their poor performance'), which weakens the comparison.\n\nOverall: a serious method paper that would get a conditional accept from me. The authors should repair the formal propositions—either redefine non-leakage to exclude self-loops or restrict the claim to the two-stage architecture—and add the missing baselines or state they're omitted. The practical contribution stands on its own. Read it if you work on order-robust ICL or attention masks. I'd bring it to a reading group as a good example of a neat architecture outpacing its formal motivation, and yes, it deserves a real referee.","headline":"InvICL is a clever and empirically useful architecture, but its formal non-leakage characterization contradicts the paper's own definition and the 'principled design' story doesn't hold as written.","tokens_in":23914,"tokens_out":9850,"would_cite":true,"duration_ms":87591,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that in-context learning can be made invariant to the order of context examples without sacrificing accuracy, by giving each example a leave-one-out encoding that never sees its own label yet still depends on all other…","keywords":["in-context learning","permutation invariance","information non-leakage","context interdependence","attention mask","leave-one-out encoding","length generalization","prompt order sensitivity"],"falsifier":"Run the paper's own definition as a probe on a model with the diagonal (bag-of-examples) mask: fix all context examples except one, flip that example's label $y_i$, and check whether the model's prediction for that same example $x_i$ changes. If it changes, the diagonal mask leaks under Definition 3.2 and Proposition 3.6 fails, so the claimed principled derivation of the two-stage design collapses even if the implemented InvICL architecture remains non-leaky.","tokens_in":2110,"feed_emoji":"🧠","tokens_out":3169,"duration_ms":173428,"temperature":0.7,"pith_summary":"The paper's target is a class of algorithms for in-context learning (ICL) in which the model's prediction for a test query is unchanged when the order of the context examples is permuted. The authors claim that previous invariant ICL methods underperform standard auto-regressive ICL because they sacrifice one of two properties: information non-leakage, meaning the prediction for each example never sees that example's own label, and context interdependence, meaning each example's encoding depends on the other examples. The paper proposes InvICL, a two-stage scheme with leave-one-out encodings, and reports that it satisfies permutation invariance, non-leakage, and interdependence simultaneously. Empirically, it reports accuracy gains over both invariant and non-invariant baselines on most of a large benchmark suite, plus better length extrapolation and out-of-distribution generalization.","feed_headline":"Invariant ICL beats standard in-context learning on most tasks","feed_subtitle":"Predictions never see their own labels, yet each example still informs the others; out-of-distribution accuracy rises.","key_machinery":"The central object is the attention mask over context examples, interpreted as the adjacency matrix of a message-passing digraph. The argument runs on three equivalences: permutation invariance holds if and only if the mask is one of three constant patterns (full, diagonal, or off-diagonal); information non-leakage holds if and only if the mask can be reordered to lower-triangular, meaning the message-passing graph is acyclic; and the conjunction of the two forces a diagonal, bag-of-examples mask, in which no context example attends to any other. To recover interdependence, the paper introduces the leave-one-out (LOO) attention mask as the carrying mechanism: each example is first encoded by its own bag-of-examples attention so that its encoding never contains its own label, then re-encoded by attending to all other examples' independent encodings, and finally the test example aggregates the LOO encodings. A duplicated-input 'unrolling' runs both stages in a single forward pass at the same $O(n^2)$ attention complexity as the baselines.","core_discovery":"The paper's central claim is that the three desiderata an invariant ICL algorithm should satisfy—permutation invariance, information non-leakage, and context interdependence—are jointly achievable, and that earlier invariant methods underperform because each sacrifices one of the last two. The paper proves a mask-level characterization: over the context examples, permutation invariance forces the attention mask into one of three forms (full attention, strictly diagonal, or strictly off-diagonal); information non-leakage forces the message-passing graph to be reorderable to lower-triangular; and the intersection of these conditions is a diagonal, bag-of-examples mask in which each example is aggregated independently. Interdependence is then restored in a second stage: each example is pre-encoded by bag-of-examples attention over all other examples but itself (a leave-one-out encoding), and the test example attends to these leave-one-out encodings. The paper claims that this design, implemented in parallel by duplicating the input sequence, outperforms auto-regressive, prefix, and bag-of-examples ICL on most of 142 real-world tasks, with the largest advantages in out-of-distribution settings and in length extrapolation beyond the trained number of demonstrations.","pith_inferences":["I would flag that the proof of Proposition 3.5 (Appendix D.3) explicitly allows self-loops on the diagonal when declaring the mask lower-triangular, and a diagonal self-attention entry lets an example attend to its own value, which encodes its own label; on the strictest reading of Definition 3.2 that is leakage, so the formal derivation of the two-stage design is weaker than the implemented archi","Proposition 3.4's third mask (cross-attention between different examples with no self-attention) is invariant, but the paper's own acyclicity criterion marks it as leaky because pairs of examples share edges in both directions; testing whether that mask actually copies labels would probe whether the directed-acyclic-graph condition is the right formalization of information non-leakage.","The optimization analysis suggests a measurement the paper does not report: since Theorem C.1 says InvICL tracks full gradient descent, its in-context predictions on synthetic linear regression should approach the least-squares estimator more closely than auto-regressive ICL's do, and that gap could be quantified directly."],"forward_implications":["Prompt-order sensitivity in ICL becomes a solved problem in the settings tested: InvICL reports zero order sensitivity under random permutations, so expensive search for a good prompt ordering becomes unnecessary.","Length generalization improves: models meta-trained with 8 demonstrations stay accurate from 1 to 16 demonstrations, and synthetic models trained on 40 in-context examples extrapolate beyond 40 where auto-regressive ICL degrades.","Out-of-distribution accuracy is where invariance pays most: on target tasks in unseen domains, InvICL beats every non-invariant baseline on all seven settings, and every invariant baseline on six of the seven.","The invariance comes at the same asymptotic cost: the duplicated-input parallel implementation keeps inference time and $O(n^2)$ attention complexity at the level of prefix or bag-of-examples ICL.","From the gradient-descent perspective, InvICL approximately implements full gradient descent on the regression objective, differing only by a second-order term, whereas auto-regressive ICL emulates online gradient descent and bag-of-examples ICL computes gradients only at the initial point."],"supporting_citations":[{"why":"defines Prefix ICL, the full-attention invariant design that the paper identifies as leaky, and supplies the T5 architecture whose attention mask SAICL adapts.","marker":"Raffel et al., 2020"},{"why":"introduces PCW, the parallel-context-window bag-of-examples ICL whose independently encoded examples define the diagonal-mask family.","marker":"Ratner et al., 2022"},{"why":"BatchICL, the order-agnostic one-shot-encoding baseline that motivates the comparison settings of Figure 1 and Table 2.","marker":"Zhang et al., 2024"},{"why":"SAICL, the structured-attention bag-of-examples variant that the paper's Table 2 must beat among invariant baselines.","marker":"Cai et al., 2023"},{"why":"supplies the synthetic linear-regression task, the 12-layer decoder architecture, and the in-context training objective used for the convergence and length-extrapolation experiments.","marker":"Garg et al., 2022"},{"why":"supplies the 142-task meta-training and evaluation framework that produces all real-world benchmark numbers.","marker":"Min et al., 2022b"},{"why":"NoPE, the no-positional-encoding baseline that separates ordering effects caused by the causal mask from those caused by positional encoding.","marker":"Kazemnejad et al., 2024"},{"why":"supplies the directed-acyclic-graph characterization that Proposition 3.5 uses to equate information non-leakage with a lower-triangular reorderable mask.","marker":"Zheng et al., 2018"},{"why":"provides the attention parametrization under which Theorem C.1 shows InvICL approximately implements gradient descent.","marker":"Von Oswald et al., 2023"}],"fun_headline_variants":["InvICL: invariant ICL that still uses full context and stays private","Leave-one-out encoding gives ICL invariance and interdependence","InvICL beats standard ICL and prior invariant methods on most tasks","Permutation-invariant ICL now matches auto-regressive performance"],"cache_read_input_tokens":25984,"weakest_assumption_plain":"The load-bearing premise is that an example attending to itself in the attention mask does not count as leaking its own label; if self-attention is treated as leakage, the proof that a diagonal mask preserves non-leakage, and with it the derivation of the two-stage leave-one-out design, no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["InvICL: invariant ICL that still uses full context and stays private","Leave-one-out encoding gives ICL invariance and interdependence","InvICL beats standard ICL and prior invariant methods on most tasks","Permutation-invariant ICL now matches auto-regressive performance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000351,"raw_usage":{"total_tokens":1923,"prompt_tokens":964,"completion_tokens":959,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":885}},"tokens_in":580,"tokens_out":959,"duration_ms":8345,"temperature":1.0,"reasoning_tokens":885,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:17:26.805757+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's own definition as a probe on a model with the diagonal (bag-of-examples) mask: fix all context examples except one, flip that example's label $y_i$, and check whether the model's prediction for that same example $x_i$ changes. If it changes, the diagonal mask leaks under Definition 3.2 and Proposition 3.6 fails, so the claimed principled derivation of the two-stage design collapses even if the implemented InvICL architecture remains non-leaky.","supporting_citations":[{"cited_title":"What can transformers learn in-context? a case study of simple function classes","cited_arxiv_id":null,"evidence_quote":"supplies the synthetic linear-regression task, the 12-layer decoder architecture, and the in-context training objective used for the convergence and length-extrapolation experiments."},{"cited_title":"The impact of positional encoding on length generalization in transformers","cited_arxiv_id":null,"evidence_quote":"NoPE, the no-positional-encoding baseline that separates ordering effects caused by the causal mask from those caused by positional encoding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the directed-acyclic-graph characterization that Proposition 3.5 uses to equate information non-leakage with a lower-triangular reorderable mask."}],"review_version":1}