Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913938437832704 |
|---|---|
| author | Lewis, Owen Ghani, Neil Dudzik, Andrew Perivolaropoulos, Christos Pascanu, Razvan Veličković, Petar |
| author_facet | Lewis, Owen Ghani, Neil Dudzik, Andrew Perivolaropoulos, Christos Pascanu, Razvan Veličković, Petar |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_08796 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists Lewis, Owen Ghani, Neil Dudzik, Andrew Perivolaropoulos, Christos Pascanu, Razvan Veličković, Petar Programming Languages Machine Learning 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. |
| title | Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists |
| topic | Programming Languages Machine Learning |
| url | https://arxiv.org/abs/2507.08796 |