Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists

Andrew Dudzik; Christos Perivolaropoulos; Neil Ghani; Owen Lewis; Petar Veli\v{c}kovi\'c; Razvan Pascanu

REVIEW 3 major objections 5 minor 6 references

Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Any list function that commutes with value-based deletion is fully determined, on inputs with at least three distinct values, by its outputs on sublists with only two distinct values.

desk verdict Genuinely new class and a likely-correct determination theorem, but the flagship one-pass amalgamation proof has a real gap for larger inputs, and Lemma 4.5 overclaims. read the letter →

arxiv 2507.08796 v1 pith:PABGMUB6 submitted 2025-07-11 cs.PL cs.LG

Owen Lewis , Neil Ghani , Andrew Dudzik , Christos Perivolaropoulos , Razvan Pascanu , Petar Veličković This is my paper

classification cs.PLcs.LG

keywords filterequivariancelengthgeneralizationlistfunctionsamalgamationsemi-simplicialsetsnaturaltransformationsextrapolationneuralsequencemodels

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a principled answer to the question of what it means for a list function to extrapolate from short examples to arbitrary lengths: the function should commute with value-based deletion. It introduces filter-equivariant functions, which satisfy $f\circ \mathrm{filter}_\phi = \mathrm{filter}_\phi\circ f$ for every predicate $\phi$, and shows this symmetry is a real constraint: such functions are fully determined, on lists with at least three distinct values, by their values on sublists containing only two distinct values. The centrepiece is the amalgamation algorithm, which reconstructs $f\,xs$ by taking a majority vote over the images of filtered sublists. If right, this turns length-general extrapolation from a philosophical puzzle into a computable procedure, and gives a concrete symmetry to build into neural sequence models. The paper also shows that the more restrictive natural filter-equivariant functions are determined by a single length-two example and that exactly $2\cdot 3^{k-1}$ of them exist for each inflation factor $k$.

What carries the argument

The central mechanism is the amalgamation algorithm ($amal$). Given a collection $\chi: X\to [X\setminus\{x\}]$ of lists, each obtained by deleting a distinct element $x$ from the target list, $amal$ reads off the unique head element that appears first in all lists still containing it, appends it, removes it from every list, and recurses; the predicate $AM$ encodes the coherence condition that guarantees uniqueness of this majority vote. The paper proves that the one-deletion map $\pi$ is an isomorphism between $[X]$ and $AM$, and that for a filter-equivariant $f$ the collection $\pi(f\,xs)$ remains amalgamable, so $f\,xs = amal(\pi(f\,xs))$. The occurrence function $\Phi(x,n) = len(f(\mathrm{repeat}_n\,x))$ supplies elementwise multiplicities, and the semi-simplicial cone characterisation (with $k$-semi-simplicial permutations for NFEs and cones over $Perm\cdot\hat{\Phi}$ for general FEs) supplies the coherence laws across lengths.

What would settle it

Take a concrete FE function such as reverse or sort, fix a list with three or more distinct values, compute $f$ on all two-unique sublists, run $amal$, and compare with $f\,xs$; any mismatch would falsify Theorem 5.3. More aggressively, a brute-force search over all functions on a finite alphabet up to length $N$ that satisfy every filter-commutation equation would find none that disagrees with $amal$ reconstruction if the theorem is true, and the first such function would disprove it.

Watch

Extended reading notes

Core claim

Every filter-equivariant function $f: [a]\to[a]$—one that commutes with every value-based deletion $\mathrm{filter}_\phi$ in the sense $f\circ \mathrm{filter}_\phi = \mathrm{filter}_\phi \circ f$—is length-general in a precise computational sense. Theorem 5.3 states that when the input list $xs$ has at least three distinct elements, $f\,xs$ can be reconstructed exactly from the collection $\{f\,ys\}$ where $ys$ ranges over all sublists of $xs$ with two unique elements. The reconstruction is performed by the amalgamation algorithm, which determines the next output element by majority vote over the filtered images and strips it off recursively. For natural filter-equivariant functions (which are also map-equivariant), a single length-two example determines the function on every input. The paper characterises these classes via semi-simplicial cones and counts the $k$-NFEs: there are $2\cdot 3^{k-1}$ of them for $k\ge 1$.

Load-bearing premise

The load-bearing premise is that filter equivariance—commuting with every value-deleting filter—is the right symmetry to demand of a rule-following list function, and without it (or on inputs with fewer than three distinct values) the extrapolation guarantee does not follow.

Editorial extensions

If this is right

Any FE function can be evaluated on long lists using only an oracle for two-unique sublists, so extrapolation to arbitrary length is exact and algorithmic.
For natural filter-equivariant functions, a single observed doubleton example pins down the function on all lists, including inputs with repeated elements after enumeration.
The finite count of $k$-NFEs ($2\cdot 3^{k-1}$ for $k\ge 1$) means the natural filter-equivariant functions form a small, enumerable design space for sequence models.
FE functions cannot introduce values absent from the input, so learned or constructed FE functions are guaranteed not to hallucinate new tokens.
Because all FEs share the same amalgamation step, the only remaining degree of freedom is the base case on two-unique-element lists, exactly like a recursion with no free step function.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

I read the theorem as giving a quantitative, algorithmic answer to the quus-style skeptical challenge for list functions: once filter equivariance is imposed, long-list behaviour is not merely consistent with short-list data but forced by it.
A testable extension, beyond the paper's claims, is that neural sequence models encouraged to be approximately filter-equivariant (for example through data augmentation with value-deletion filters) should show improved length generalisation outside the training range.
The three-distinct-values condition identifies a boundary: behaviour on lists with one or two distinct values is an unaxiomatised base case, so any practical use of FE must supply that base behaviour separately.
The majority-vote structure of $amal$ resembles consensus and error-correcting reconstruction, suggesting that noisy or approximate filter equivariance might be studied by the same amalgamation machinery.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline result is real: the filter-equivariant class is new, and the claim that an FE function on lists with at least three distinct values is determined by its behavior on two-value sublists is the kind of thing that deserves to be worked out. I step-checked the main chain (Lemma 3.3, Lemma 5.2, the delta definition, and the worked example), and it holds. The simplicial account of NFEs and the count 2·3^{k−1} are genuinely new, and the paper is honest about scope: it doesn't claim to solve induction, it names non-FE functions like ripple-carry, and it gives the multiplicity-squared counterexample that blocks the NFE-style single-example inference for general FEs.

Now the soft spots, in proportion. Lemma 4.5 overclaims: it says every FE is a cone over Perm·Φ-hat, but sort is FE and is not such a cone, because the cone has to assign one permutation to a multiset regardless of the actual values, while sort's permutation depends on the order of those values. That is a real mistake in the paper, and it is the kind that should have been caught by testing the statement against their own example. The bigger gap is in the proof of the single-pass amalgamation. Lemma 5.4 only collapses two nested amal levels. For an input with more than four unique values, the recursion in Theorem 5.3 produces more than two nested amals, and the lemma does not show that all of them can be flattened into one amal over all two-value sublists. The nested-amalgamation argument does establish determination, so the theorem's conclusion is probably still true, but the paper's pseudocode claims a single pass and the proof does not deliver it. The authors should provide a projection lemma or argue directly that amal over pairwise value-projections reconstructs any word.

Several supporting lemmas (3.10, 3.11, 4.2) are sketched, not fully proved; the count in 3.11 is plausible but needs a rigorous induction. The ML promise is untested.

Who gets value: people working on geometric/categorical deep learning, functional-programming semantics of list transformations, and length generalization. It deserves a serious referee. I would send it to review, but ask for a corrected Lemma 4.5 and a complete proof of the one-pass amalgamation. If those get fixed, the paper is solid.

Referee Report

3 major / 5 minor

Summary. The paper introduces filter-equivariant (FE) functions, i.e. list functions f:[a]->[a] that commute with every value-based filter, and natural filter-equivariant (NFE) functions that additionally commute with every map. It proves structural properties of FEs, develops a categorical/simplicial description of NFEs and FEs, and presents an inductive characterization of NFEs. The headline contribution is the amalgamation algorithm: for any FE f and any input xs with at least three unique values, the output f xs can be reconstructed from the collection {f ys}, where ys ranges over all sublists of xs with two unique elements; for NFEs, a single length-two example is claimed to determine the function on all inputs. The paper positions this as a symmetry-based account of length-general extrapolation and discusses potential machine-learning relevance.

Significance. If the main theorem is fully established, the paper gives a clean, nontrivial answer to a well-known puzzle about length generalization: a substantial class of list functions is uniquely and computably determined by their behavior on small sublists. The categorical framework, the explicit algorithm, and the worked examples make the contribution accessible and potentially influential for the theory of equivariant sequence functions. The classification of NFEs (2*3^{k-1}) and the connection to semi-simplicial sets are elegant and novel. The paper is refreshingly explicit about what is an axiom and what is a theorem, and the ML motivation is clearly labeled as future work rather than as a demonstrated result.

major comments (3)

[Section 5.3, Theorem 5.3 and Lemma 5.4] The one-pass amalgamation claim is not proven for inputs with more than four unique elements. Lemma 5.4 equates a two-level nested amal with a single amal over a collection indexed by pairs (x,y) whose entries are f(filter(≠{x,y}) xs); this filter removes exactly two values, so for |X|=5 each list in the right-hand collection retains three unique values. The theorem statement and the pseudocode, by contrast, use sublists that keep exactly two unique values. The written proof therefore does not reduce the fully nested expression to a single amal over all C(|X|,2) two-unique sublists. Please provide the missing projection lemma (e.g., that amal over all pairwise value-projections reconstructs any word over X when |X|≥3, then use filter equivariance to transfer it to f), or explicitly restrict the theorem to |X|=4.
[Proof of Lemma 5.4] The induction step in Lemma 5.4 is not formally justified. The amalgamability predicate AM is defined only for collections indexed by X; for the pair-indexed collection χ′ the proof introduces a modified δ but never defines the corresponding AM predicate or verifies that δχ′ lies in it. The sentence 'it holds (by induction on f xs, as in Lemma 5.1)' needs a statement of the generalized induction hypothesis, which must cover collections indexed by all pairs (and, after one step, by the resulting smaller subsets). As written, the proof does not establish that the algorithm terminates correctly on the pair-indexed collection when tail(f xs) has fewer than four unique elements.
[Section 4, Lemma 4.5] Lemma 4.5, 'A Φ-FE function is a cone over the functor Perm·Φ-hat', is stated without proof. This lemma is the formal characterization of filter equivariants in terms of coherent permutations and is a central claim of Section 4, even though it is not used in the amalgamation argument. Please provide the proof, or explicitly mark the statement as a conjecture, since the surrounding text currently presents it as an established theorem.

minor comments (5)

[Throughout] The notation |xs| is used for both the length of a list and the set of its unique elements (e.g., in Lemma 5.2 and Lemma 5.4). This is confusing; please use distinct notation such as support(xs) or set(xs), and reserve |·| for cardinality.
[Section 5.3 pseudocode] The pseudocode states 'Require: |X| ≥ 3' but X is never defined in the algorithm block. It should say 'let X be the set of unique elements of xs' and use that consistently.
[References] The citation [GDL] in Definition 2.1 does not appear in the reference list; the later citation [GLD+24] uses a different key. Please unify the reference keys.
[Section 3.2, Lemma 3.10] The bijection between NFE and List(Nat+Nat) is a bijection between syntactic representations, not denotations; the text hints at this but could state it more explicitly to avoid confusion.
[Figure 2] The caption describes the algorithm as producing [y1,...,y5] but the pseudocode returns reverse(ys); please clarify the relationship between the figure's y_i and the algorithm's accumulator ys.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the extrapolation theorem is derived from the filter-equivariance axioms and proven reconstruction properties, not from fitted inputs or self-citations.

full rationale

The central claim (Theorem 5.3) is derived, not assumed. The paper defines filter equivariance in Definition 2.3 (Eq. 5), defines the amalgamability predicate AM_X and the algorithm amal in Section 5.1, and proves in Lemmas 5.1–5.2 that π sends lists into AM_X with amal as inverse and that this is preserved by filter-equivariant functions. Theorem 5.3 then combines these lemmas with the equivariance equation f(filter(≠x)xs) = filter(≠x)(f xs) to show that f xs can be reconstructed from values on filtered sublists. This is a mathematical derivation, not a fit: no parameter is fitted to data and then renamed a prediction. The NFE specialization uses map equivariance to transfer a single length-two example to all length-two examples, and the semi-simplicial cone characterization is an internal equivalence, not an imported uniqueness theorem. The paper's self-citations ([BBCV21], [GLD+24], [LH19], [DvGPV24]) appear as background or future-work pointers and do not carry the uniqueness or extrapolation load. Any concern about Lemma 5.4's one-pass collapse for inputs with more than four unique values is a proof-completeness issue, not a circular reduction; it does not amount to defining the target in terms of the prediction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 3 invented entities

The paper introduces no fitted parameters: Phi is a structural characterization, and k labels a class, not a constant fitted to data. Axioms are the standard parametricity background, the modeling choice that filter equivariance captures rule-following extrapolation, and the coherence/cone structure imposed on rearrangements. Invented entities: the FE class and the amalgamation algorithm carry their own proof obligations and are checkable; the Bag category is defined cleanly, but the cone characterization built on it (Lemma 4.5) is not supported for value-dependent FEs like sort.

assumptions (3)

standard math Parametrically polymorphic functions of type [a] -> [a] are exactly natural transformations of the list functor (map-equivariant functions).
Invoked in Section 2.1 to identify map-equivariant functions with parametric polymorphism; relies on relational parametricity / free theorems, stated as a standard result without proof.
domain assumption Filter equivariance is a faithful formalization of rule-following that supports length generalization for list functions.
The paper's central modeling choice (Sections 2.2-2.3): value-based removal via filter, rather than position-based removal (tail), is argued by examples (tail excludes reverse and sort); this is a design judgment, not a theorem.
domain assumption The semi-simplicial cone coherence condition exactly captures the coherence of rearrangements required by filter equivariance.
Used in Lemma 3.7 and the NFE characterization: the cone condition over Perm (permutations restrict when elements are removed) formalizes 'same behavior on sublists'; the equivalence is asserted rather than derived, and Lemma 4.5's extension to general FEs is too strong for value-dependent functions like sort.

invented entities (3)

Filter-equivariant (FE) function class independent evidence
purpose: Defines the semantic class of list functions preserved under all value-based removals (filter predicates); the paper's central object of study.
The class yields checkable consequences independent of the paper: the amalgamation algorithm's outputs on examples (Section 5, e.g. f[3,2,1,2] = [1,2,2,3]) can be computed and verified; the class is a definition whose content is the theorem proved about it.
Category Bag (multiset category)
purpose: Purported domain for the cone characterization of general FEs (Definitions 4.3-4.5).
Definition is self-contained, but the load-bearing claim built on it (Lemma 4.5) fails as stated for value-dependent FEs such as sort, which assigns different rearrangements to [3,5] and [5,3], the same Bag object; so Bag is not supported as the right structure for general FEs.
Amalgamation algorithm (amal) independent evidence
purpose: Constructs f xs from f on two-unique-element sublists; the paper's highlight result.
The algorithm is fully specified (pseudocode, Section 5.3) with a hand-checkable worked example, so its correctness is independently verifiable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists." pith.science (2026). https://pith.science/paper/PABGMUB6

@misc{pith2026250708796,
  author       = {Pith},
  title        = {Pith review of: Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PABGMUB6}},
  note         = {Machine review of arXiv:2507.08796}
}

read the original abstract

What should a function that extrapolates beyond known input/output examples look like? This is a tricky question to answer in general, as any function matching the outputs on those examples can in principle be a correct extrapolant. We argue that a "good" extrapolant should follow certain kinds of rules, and here we study a particularly appealing criterion for rule-following in list functions: that the function should behave predictably even when certain elements are removed. In functional programming, a standard way to express such removal operations is by using a filter function. Accordingly, our paper introduces a new semantic class of functions -- the filter equivariant functions. We show that this class contains interesting examples, prove some basic theorems about it, and relate it to the well-known class of map equivariant functions. We also present a geometric account of filter equivariants, showing how they correspond naturally to certain simplicial structures. Our highlight result is the amalgamation algorithm, which constructs any filter-equivariant function's output by first studying how it behaves on sublists of the input, in a way that extrapolates perfectly.

Figures

Figures reproduced from arXiv: 2507.08796 by the authors.

**Figure 1.** We leverage filter equivariance as a way to express functions which are length-invariant through removing items by value. Generally, a filter-equivariant (FE) function f may be composed with filter in any order, yielding the same results at the end. Now, consider what happens if instead we focus on reducing a list’s length by removing an element. For example, consider the tail function, which removes the first eleme… view at source ↗

**Figure 2.** The process of amalgamating the output of [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

6 extracted references · 5 canonical work pages

[1]

Geometric deep learning: Grids, groups, graphs, geodesics, and gauges

Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veli c kovi \'c . Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478 , 2021

arXiv 2021
[2]

Asynchronous algorithmic alignment with cocycles

Andrew Joseph Dudzik, Tamara von Glehn, Razvan Pascanu, and Petar Veli c kovi \' c . Asynchronous algorithmic alignment with cocycles. In Soledad Villar and Benjamin Chamberlain, editors, Proceedings of the Second Learning on Graphs Conference , volume 231 of Proceedings of Machine Learning Research , pages 3:1--3:17. PMLR, 27--30 Nov 2024

work page 2024
[3]

Position: Categorical deep learning is an algebraic theory of all architectures

Bruno Gavranovi\' c , Paul Lessard, Andrew Joseph Dudzik, Tamara Von Glehn, Jo\ a o Guilherme Madeira Ara\' u jo, and Petar Veli c kovi\' c . Position: Categorical deep learning is an algebraic theory of all architectures. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,...

work page 2024
[4]

Permutation equivariant models for compositional generalization in language

Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivariant models for compositional generalization in language. In International Conference on Learning Representations , 2020

work page 2020
[5]

Saul A. Kripke. Wittgenstein on Rules and Private Language: An Elementary Exposition . Harvard University Press, Cambridge, 1982

work page 1982
[6]

Data for free: Fewer-shot algorithm learning with parametricity data augmentation, 2019

Owen Lewis and Katherine Hermann. Data for free: Fewer-shot algorithm learning with parametricity data augmentation, 2019

work page 2019

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Geometric deep learning: Grids, groups, graphs, geodesics, and gauges

Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veli c kovi \'c . Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478 , 2021

arXiv 2021

[2] [2]

Asynchronous algorithmic alignment with cocycles

Andrew Joseph Dudzik, Tamara von Glehn, Razvan Pascanu, and Petar Veli c kovi \' c . Asynchronous algorithmic alignment with cocycles. In Soledad Villar and Benjamin Chamberlain, editors, Proceedings of the Second Learning on Graphs Conference , volume 231 of Proceedings of Machine Learning Research , pages 3:1--3:17. PMLR, 27--30 Nov 2024

work page 2024

[3] [3]

Position: Categorical deep learning is an algebraic theory of all architectures

Bruno Gavranovi\' c , Paul Lessard, Andrew Joseph Dudzik, Tamara Von Glehn, Jo\ a o Guilherme Madeira Ara\' u jo, and Petar Veli c kovi\' c . Position: Categorical deep learning is an algebraic theory of all architectures. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,...

work page 2024

[4] [4]

Permutation equivariant models for compositional generalization in language

Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivariant models for compositional generalization in language. In International Conference on Learning Representations , 2020

work page 2020

[5] [5]

Saul A. Kripke. Wittgenstein on Rules and Private Language: An Elementary Exposition . Harvard University Press, Cambridge, 1982

work page 1982

[6] [6]

Data for free: Fewer-shot algorithm learning with parametricity data augmentation, 2019

Owen Lewis and Katherine Hermann. Data for free: Fewer-shot algorithm learning with parametricity data augmentation, 2019

work page 2019