acceptodds
Under review as a conference paper at ICLR 2027

MARSEA: MULTIVARIATE RELATIONS BY SELECTIVE EXCLUSION IN ATTENTION

Abstract

Attention represents relations pairwise: Aij is a statement about one query and one key. Under multivariate competitive exclusion a set of candidates jointly bears on a target and competes for a finite influence budget, settled by comparison within the set: the winner takes the bulk, close rivals less, everything past a content- decided cutoff exactly none. We prove four things about this class. Separation: no query-local scheme — rows computed independently per query, as in softmax with any positional bias or element-wise gate — can enforce a non-product-form constraint on a key’s degree. Conservation: no row-normalized scheme can bound every key’s fan-out below nq /nk , and doubly stochastic attention meets that bound only by giving every key the same content-free fan-out. A precision identity: with m gold items among n candidates, every full-support attention has evidence precision exactly m/n, whatever the scores. Sharp recovery: a sparsemax program over a relation slice returns the gold support exactly iff its exclusivity τ lies in [1/(W + mδ), 1/W ), for score margin δ and within-set spread W ; it degrades weakest-first above the interval, and the interval only widens as the slice shrinks. MarSea is the mechanism these results leave room for. On the query or the key margin it places a bounded-size relation and, at each constrained element, one closed-form program that inherits the base normalizer’s mass on the relation and re-shapes it by sparsemax, so members can receive exactly zero, under a shape control τ and a mass control λ. The query-local row form can learn a partition but not enforce one; the query-coupled column form can, and under causal de- coding its exclusions are permanent. We deploy the row form on a softmax-one base and ablate the column form. On multi-value retrieval with a 1.5B decoder (three seeds), MarSea matches or exceeds softmax, softmax-one, causal learned- marginal transport and row-wise sparsemax on exact-set accuracy, precision and re- call at every list length, with the fewest repeated and omitted values on 32-value lists; it beats softmax’s exact-set accuracy by 6 and 13 points at 16 and 32 values, its margin over softmax-one alone is within seed variance, and row-wise sparsity alone hurts.

Primary area:
learning theory
Keywords:
expressivity of transformers, representational limitations of attention, sparsemax, sparse attention, exact support recovery, doubly stochastic attention, attention mechanisms, softmax limitations

Reviews

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

The paper studies how attention can represent competition and exclusion among candidates. MarSea applies sparsemax within selected relation sets, with row and column forms for different constraints. The theory analyzes query-local limitations and exact support recovery. Experiments use a 1.5B decoder on retrieval tasks with three seeds. Results improve over ordinary softmax, while gains over softmax-one remain within seed variability.

Critical strengths

The distinction between selection within a row and coordination across queries is useful. The theory helps explain why changing attention scores alone may not provide the desired structural constraints. The row/column comparison and relation-off controls also help separate structural enforcement from behavior learned during training.

Critical weaknesses

The main experimental result is not clearly better than softmax-one. The deployed row form also remains inside the query-local class criticized by the theory, while the column form does not show a clear advantage. The paper therefore offers a stronger theoretical motivation than its experiments support. It remains unclear whether the proposed mechanism provides enough practical benefit to justify its added complexity.

Questions for authors
  1. Theorem 1 allows a product-form attainable set to lie inside a non-product constraint set. What additional condition rules out satisfying a column capacity through conservative per-query bounds? This matters to the scope of the impossibility claim.
  2. Given the lack of a clear gain over softmax-one, which reported result best establishes the practical value of MarSea beyond its theoretical contribution?
1 comment

Thank you for the insights.

Theorem 1: what rules out satisfying a column capacity through conservative per-query bounds? Theorem 1 alone does not, and that case is what "except vacuously" refers to. A query-local scheme can satisfy Σᵢ Aᵢⱼ ≤ c on every input by capping each query's weight on key j at c/n_q. Each attainable set Rᵢ then lies in [0, c/n_q], and the product of the Rᵢ lies inside the constraint.

What rules it out is the non-degenerate replication assumption used in the capacity corollary. Suppose the scheme can, on admissible inputs, give key j a weight of at least a at M queries. In particular, suppose any single query can select key j, which the paper's proposition on local selection grants every query-local scheme. Then the product set contains a point with M coordinates of at least a, and the capacity fails whenever c < M·a. Conservative bounds satisfy the constraint only by giving up selection: no query could place more than c/n_q of its mass on the key it needs. App. J.8 of the revised PDF states this.

The main result is not clearly better than softmax-one. True of the submission. The cause was our implementation of the relation module, not the mechanism (general response). The submitted relation held 8% of the correct candidates at the rows that decide the list; the corrected one holds 99.8% and excludes values already listed (below). With the corrected module, MarSea reaches .988 exact-set on RULER's default layout against .925–.933 for softmax, softmax-one and the submitted version (32 values: .973 against .74–.78), with every seed above every baseline seed.

The deployed row form is query-local; the column form shows no clear advantage.

The corrected relation models a relation across rows. In multi-value listing, the rows that start a value and the values of the queried key stand in a one-to-one relation: each such row copies one value, and each value is to be listed once. This is a constraint across rows, of the non-product form that Theorem 1 is about. The corrected relation models it by a causal route: which values have been listed is read from the generated text, and those values are excluded from the relation of every later row. Row i's attention is therefore a function of what earlier rows emitted. Information passes between rows through the emitted text, not through attention mass.

How this stands with Theorem 1. The theorem assumes that the rows' inputs can be set independently. The causal route removes that independence by construction, so the theorem's impossibility does not bind the mechanism in decoding: the coupling the theorem shows to be necessary is supplied by the decoding loop. Within a single attention operation, with the listed signal taken as given, the row form is still query-local in the sense of Def. 1. And the exclusion is soft (listed keys keep 20% of their base attention), so "no value listed twice" is met in practice, not guaranteed: it holds on all 1,500 evaluation lists of the corrected relation, against .08–.78 repeats per 32-value list for the baselines.

The column form. The theory does not rest on it. The paper gave it too much weight in its presentation, as if it were the way to model a one-to-many relation. Such a relation can be modelled in either form, with the program on the row's slice of keys or on the key's slice of rows; "column form" names the orientation in which the row is the one end. Theorem 1 states the limit of a row-local program and stands whatever the column form's empirical result. As submitted it shows no advantage (.939 on the default layout against .933 for the submitted row form), and its implementation is weaker than the row form's: it marks ownership of a key by attention mass, which is unreliable before a value is emitted. The fair reference for its performance is the row form's machinery with rows and keys exchanged. That run did not finish within the discussion period; we make no claim for it here and will report it in the final version.

Which reported result best establishes practical value? In the submission, the reduction of repeated values at 32 values (from .31 to .21 per list against softmax-one). The result that now establishes it is the corrected relation: about five times fewer failed lists than any baseline on RULER's default layout (9 of 750 against 50–56).

Complexity. The correction adds about 0.4M parameters to a 1.5B-parameter backbone. It costs time at inference: decoding a 4K-token prompt with 32 values takes 14.7 s per list with softmax-one, 16.3 s with the submitted MarSea and 25.8 s with the corrected MarSea (1.75 times softmax-one, same GPU). Against it stand about five times fewer failed lists.

Presentation. We take the score of 1 seriously. The revised PDF of this period adds App. J only; the final version will rewrite Secs. 1–3 with a notation table and a running example.

Reviewer_gaFsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper discusses attention mechanisms and ways to improve current softmax-type baselines.

The theoretical directions suggested are useful and somewhat interesting, but the contribution appears limited at this point. The exact sparsemax recovery interval is perhaps the most useful result. It provides a clean explanation of sharpening. Nevertheless, it follows fairly directly from the existing sparsemax support characterization and assumes that the candidate relation already contains the true targets and ranks every target above every distractor, without sufficient validation that training could do so.

The empirical evidence for the method’s benefit is not convincing: the column-based mechanism, which the paper strongly motivates, does not establish a noticeable advantage over the row form. MarSea’s exact-set accuracy gain over softmax-one is within the reported experimental variability.

The writing style is often punchy and aphoristic, hindering readability. The frequent lack of explicit signposting blurs what is known from prior work versus what is newly contributed.

On the positive side, the paper provides designs using selected relations and mass-preserving interventions. The “relation-off” inference toggle experiment is informative. The authors are also unusually candid about negative results.

Overall, however, the paper’s theoretical analyses and empirical findings do not meet the bar for acceptance at ICML as is.

Questions: Please comment on the extra supervision and head-selection burden. The reported MarSea training procedure uses gold source–answer block alignments, a gold-slice training phase, and additional selection of eight relation heads, whereas softmax-one does not require the relation labels or the additional head-selection step. How much of the reported benefit depends on this extra supervision and selection?

Critical strengths

On the positive side, the paper provides designs using selected relations and mass-preserving interventions. The “relation-off” inference toggle experiment is informative. The authors are also unusually candid about negative results.

Critical weaknesses

The theoretical directions suggested are useful and somewhat interesting, but the contribution appears limited at this point. The exact sparsemax recovery interval is perhaps the most useful result. It provides a clean explanation of sharpening. Nevertheless, it follows fairly directly from the existing sparsemax support characterization and assumes that the candidate relation already contains the true targets and ranks every target above every distractor, without sufficient validation that training could do so.

The empirical evidence for the method’s benefit is not convincing: the column-based mechanism, which the paper strongly motivates, does not establish a noticeable advantage over the row form. MarSea’s exact-set accuracy gain over softmax-one is within the reported experimental variability.

The writing style is often punchy and aphoristic, hindering readability. The frequent lack of explicit signposting blurs what is known from prior work versus what is newly contributed.

Questions for authors

Question: Please comment on the extra supervision and head-selection burden. The reported MarSea training procedure uses gold source–answer block alignments, a gold-slice training phase, and additional selection of eight relation heads, whereas softmax-one does not require the relation labels or the additional head-selection step. How much of the reported benefit depends on this extra supervision and selection?

1 comment

Thank you for a precise review.

The recovery interval follows from the sparsemax support characterization. We agree, and App. J.1 of the revised PDF says so (Martins & Astudillo, 2016, for a single true partner). The results we claim as new are Theorem 1, the conservation obstruction for row-normalized schemes, and the precision identity of full-support attention. The final version will mark each result as prior work, adaptation or new.

"Assumes that the candidate relation already contains the true targets and ranks every target above every distractor, without sufficient validation." This criticism was right. We measured both halves (eight relation heads, three seeds; definitions in the general response).

  • Contains the true targets. The submitted relation held 8% of the targets at rows that start a value and 88% at rows that continue one. The corrected relation holds 99.8% and 99.9%. The causes, which are ours, are in the general response (part 1).
  • Ranks targets above distractors: continuation rows. This holds. The next token is the highest-attention key on 87% of head-rows and keeps non-zero weight on 97% (submitted: 81% and 79%).
  • Value-starting rows. It does not hold as stated, and we do not claim it. The sparse step gives exactly zero to about half of the targets, so over all keys targets are not ordered above distractors (AUC .51, against .95 for the submitted relation, whose targets outside the top-8 simply keep their base attention). This is harmless for the task: the zeros are per row, a value zeroed at one row is a target again at the next, and any unlisted value is a correct next copy. What matters is the key on top, and it is a target on 67% of head-rows against 35% (39% on the same checkpoints with the relation switched off, so the concentration is the relation's doing).

App. J.1 scopes the recovery result to the continuation case and lets the end-to-end result speak for the rest.

MarSea's gain over softmax-one is within the reported variability. True of the submission, and on RULER's default layout the submitted MarSea is level with both baselines (.933 / .932 / .925). With the corrected relation it is no longer true: .988 exact-set on the default layout (32 values: .973 against .74–.78) and .972 against .883–.931 on the paper's contiguous layout. Every seed is above every baseline seed on both, and failed lists fall from 50–56 to 9 of 750.

The column form shows no advantage over the row form. Agreed for the column form as submitted (.939 on the default layout against .933 for the submitted row form). Two points. First, the theory does not rest on it. The paper gave the column form too much weight in its presentation, as if it were the way to model a one-to-many relation. It is not. Such a relation can be modelled in either form: the program sits on the row's slice of keys or on the key's slice of rows, and the theory's results on the program hold for both with rows and keys exchanged. "Column form" only names the orientation in which the row is the one end (App. J.8). Second, its performance. The submitted implementation is weaker than the row form's: it marks ownership of a key by attention mass as rows arrive (the copying row wins its column on 28% of value-starting rows). The fair reference is the row form's own machinery with rows and keys exchanged. That run did not finish within the discussion period; we make no claim for it here and will report it in the final version.

Writing. The revised PDF adds App. J only; the final version will rewrite Secs. 1–3 in plain prose, with a notation table and a running example.

Question: how much of the benefit depends on the extra supervision and the head selection?

  • Supervision. The relation's labels are the positions of the answer values in the prompt. The submission and the correction use the same annotation; they differ in the rule that turns it into targets. The gold-slice warm-up phase is kept unchanged. These losses update only the relation module's parameters; the backbone sees only the language-modelling loss, in every arm.
  • How much depends on it. For the submission, little: removing the relation at inference gives .929 / .727 against .933 / .760. For the corrected version, emptying the supervised relation at inference while keeping the listed-value exclusion lowers exact-set from .97–1.00 to .96–.98 (three seeds) and the share of head-rows with a target on top from 67% to 39%. So the supervised relation is what concentrates attention on the targets, and it adds one to three points. The causal route, which uses no labels, carries the larger part of the exact-set gain.
  • Head selection. The eight heads were chosen once, by a rule on the softmax arm's attention, and are the same in the corrected version. All baselines are patched at the same layers.
Reviewer_B2FjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

MARSEA changes how attention is distributed within a small set of learned candidates. It uses sparsemax to give some candidates zero weight. The goal is to improve source selection and reduce omissions and repetitions in retrieval. The paper provides theoretical analysis and mainly tests the method on synthetic multi-value retrieval with Qwen2.5-1.5B.

Critical strengths

Selecting a small candidate set and adjusting attention within it is a reasonable idea. The analysis explains when sparsemax can keep the correct candidates, assuming they already have higher scores than the incorrect ones.

Critical weaknesses
  1. The recovery analysis assumes that the correct candidates are retained and ranked above the incorrect ones. At the strongest probed head, the copy source is in the candidate set on 82–85% of answer rows. Attention outside the set is preserved, so a missed source does not necessarily cause a wrong answer. Please check these conditions in the main row model and relate them to the final omissions and repetitions, including cases where the source is missed.
  2. Can you show how final omissions change when the correct source is inside or outside the candidate set? A controlled test that adds or removes this source from the set, while keeping the input text unchanged, would help measure sensitivity to candidate errors.
  3. How often do the correct candidates rank above the incorrect ones in the main row model? Can this explain which examples improve when the relation is turned on? A harder retrieval setting, with longer texts or more distractors, would also help test whether this relationship holds.
Questions for authors
  1. The recovery analysis assumes that the correct candidates are retained and ranked above the incorrect ones. At the strongest probed head, the copy source is in the candidate set on 82–85% of answer rows. Attention outside the set is preserved, so a missed source does not necessarily cause a wrong answer. Please check these conditions in the main row model and relate them to the final omissions and repetitions, including cases where the source is missed.
  2. Can you show how final omissions change when the correct source is inside or outside the candidate set? A controlled test that adds or removes this source from the set, while keeping the input text unchanged, would help measure sensitivity to candidate errors.
  3. How often do the correct candidates rank above the incorrect ones in the main row model? Can this explain which examples improve when the relation is turned on? A harder retrieval setting, with longer texts or more distractors, would also help test whether this relationship holds.
1 comment

Thank you. Your three questions are the measurements we should have made before submitting.

1. Are the two conditions (retained; ranked above) met in the main row model? Pooled over the eight relation heads and three seeds, on RULER's default layout (the contiguous layout is within 3 points on every line); definitions as in the general response.

submittedcorrected
Rows that start a value
candidates in the relation (recall)8%99.8%
highest-attention key is a candidate (chance 0.3%)35%67%
candidates' share of the attention on the 8 strongest keys35%59%
Rows that continue a value
next token in the relation (recall)88%99.9%
highest-attention key is the next token81%87%
next token keeps non-zero weight79%97%
  • Retained. This failed in the submitted model at value-starting rows (8%) and holds in the corrected one. The 82–85% in the paper is a different quantity: the copy source (the value the gold lists next) at the strongest head, over all copy rows. At value-starting rows that quantity is 2% / 29% / 21% at the heads of layers 14 / 19 / 23.
  • Ranked above. Both versions hold the same number of candidates among their 8 strongest keys (about 2.4). The difference is concentration, not selection: 59% against 35% of that window's attention, and a correct key on top on 67% against 35% of head-rows.
  • One cost. At value-starting rows the sparse step gives exactly zero to about half of the candidates. The zeros are per row, a value zeroed at one row is a candidate again at the next, and any unlisted value is a correct next copy. The recovery result therefore applies as stated to continuation rows only (App. J.1 of the revised PDF).

Final errors with the corrected relation (default layout, per 32-value list): omissions .03, repeats 0.00, extras .03, against .29–.53, .23–.27 and .07–.17 for the baselines. On the contiguous layout repeats are also 0.00, while omissions stay at the baselines' level (.49 against .52–1.05).

Relation to final omissions and repeats (submitted model, 750 lists, three seeds). Omissions are 2.9 times more frequent for values whose copy source is outside the relation at their first row (repeats: 1.8 times). 74% of all omissions fall on the 45% of values that no relation head admits; none occur among the 620 values that four or more heads admit. You are right that a missed source need not cause an error: on missed rows the preserved base attention still places about .77 of its mass on the source, so only about 1% of such values are omitted.

2. A controlled test that adds or removes the source, with the text unchanged. Submitted checkpoints, three seeds, one evaluation pass over the same lists; text and weights unchanged. Per 32-value list:

relation at inferenceexact-setomissionsrepeats
as submitted.780.55.26
copy source added by a separately trained predictor.5471.18.61
relation removed (the paper's relation-off control).727.67.23

(Table 1's own pass gives .760 for the first line.)

  • Adding. At value-starting rows the copy source was in the relation on 87% of cases instead of 14%, yet omissions doubled. On 74% of those rows another member had a higher attention score, and the sparsemax gave the source exactly zero. Membership without a ranking that agrees with it hurts.
  • Removing. Omissions rise only from .55 to .67. The submitted model is nearly insensitive to its relation, which is what 8% recall predicts.

This is why the correction trains membership and ranking together and excludes the listed values.

3. Which examples improve, and a harder setting. In the submitted model, turning the relation on changes few lists (table above). In the corrected model the lists with many values improve: on the default layout it scores .987 at 16 values (baselines: .942) and .973 at 32 values (baselines: .74–.78), and failed 32-value lists fall from 33–39 of 150 to 4. Switching parts of the module off at inference on the corrected checkpoints shows where this comes from. Without the listed-value exclusion the model fails every 16- and 32-value list (14–19 repeats per 32-value list). With the exclusion kept and only the learned relation emptied, it loses 12 lists and gains 4 over three seeds, all with 16 or 32 values, and the share of head-rows with a correct candidate on top falls from 67% to 39%. So both parts contribute: the causal route carries the larger part of the exact-set gain, and the learned relation supplies the concentration on candidates and one to three points. Within the lists of Table 1 the harder axis is the number of values (1 to 32), and the ranking relationship holds along it (general response, part 2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.