CS Paper Radar

From the Transformer to a Formal Semantics of Coordinated Transformations

Marco Giunti, Fabrizia Giulia Garavaglia

cs.AI cs.CLcs.LO ·submitted 2026-10-29 10:00 UTC · v1

Abstract

We develop a formal semantics for a general class of coordinated systems of parameterized transformations, taking the Transformer as a paradigmatic starting point but abstracting from its particular mathematical instantiation. Representational vectors receive both extensional reference and ordered intensional interpretations, while parameter structures acquire relative, second-level interpretations that determine how argument properties are preserved, replaced, or combined. This yields the notion of a transforming concept: a parameterized transformation whose numerical action is coordinated with a corresponding property-level map. We then distinguish the common algebraic-semantic core of these systems from their architecture-specific functional organization, allowing different mathematical instantiations and mechanical realizations of the same abstract system type. The framework is applied to attention heads and residual connections, providing semantic explanations that depend only on the shared algebraic-semantic core and their local functional organization and therefore generalize beyond the standard Transformer. These analyses also reveal the modularity of the framework: complex architectures can be decomposed into simpler semantically coordinated subsystems whose organization may recur across different abstract system types.

Comment
v1: 28 pages, 9 sections, this version incorporates revisions made after the first round of peer review

Closest papers

Nearest neighbours by meaning across the whole index.

Foundations of Algebraic Architecture Theory: A Rising Sea of Geometry, Transport, Comparison, and Reconstruction

cs.SE cs.PL ·2026-09-23 ·Hiroyuki Nakahata
theory similarity 0.57
Abstract · 285 pages, 4 figures. Also archived on Zenodo with the same source: https://doi.org/10.5281/zenodo.22913488

AI-generated software changes make it increasingly important to determine what a change preserves, where local consistency fails to extend globally, and which alternatives remain. We develop the foundations of Algebraic Architecture Theory (AAT) from Atoms, typed primitive facts, and Laws, equations that objects must satisfy. A reading specifies what counts as structure and which operations and laws to preserve. The main reconstruction theorem identifies the category of full geometries and all their structure-preserving morphisms with an independently defined category of local models, up to equivalence. Objects are recovered up to isomorphism and morphisms between fixed endpoints uniquely. The theory addresses gluing, diagnosis, transport, classification of changes, and reconstruction. From finite Atom families we construct cores closed under operations and geometries with sites and coefficients. We give conditions under which a Cech obstruction detects the existence of a global state and, through comparison with repair semantics, a global repair. We compare diagnoses and give a finite criterion for uniform invariance given computable finite data. Transport along exact changes has a universal property and commutes with base change on exact pointed pullback squares. Comparisons of routes generated from the same square, finite comparison diagram, and geometry factor into an invertible comparison and an idempotent normalization. We characterize when observations determine comparison preservation and classify compatible lifts. Encodings of lens and protocol semantics preserve and reflect laws and recover semantics-preserving morphisms. Applications classify and count operation-preserving changes and extend morphisms uniquely from finite tables. Corresponding Lean declarations are listed in the appendix.

0.45

Hippogriff: a semantic approach to uniting core and modules

cs.PL cs.LO ·2026-08-20 ·Owen Lynch, Sam Staton
similarity 0.57
Abstract · 36 pages, including supplemental appendix

In this paper we introduce Hippogriff, a language with a module system that unifies syntax between the core level and the module level. Hippogriff's type theory is dependent, with modularity features enabled via a universe of small types, but Hippogriff still supports general recursion without making typechecking nonterminating. This paper contains two halves. In the first half, we describe Hippogriff and its implementation. In the second half, we build categorical semantics for our use of dependent types that justify the use of general recursion at the value level. Specifically, we use an extension of the second-order generalized algebraic theory framework to include a synthetic phase distinction, and this allows us to make a mathematical connection between dependent type theories and split-context type theories (like System F). Included as supplements are a Haskell implementation of Hippogriff and an appendix describing the full type theory of Hippogriff using a second-order generalized algebraic theory with phase distinction.

0.20

Scenes: A Meta-Logical Algebra for Mutable State

cs.LO ·2026-09-24 ·Simon Foster, Carlos Isasa, Christian Pardillo Laursen
hot direction similarity 0.56
Abstract · Submitted to MFCS 2026, rejected. Plan to revise and resubmit elsewhere

Modelling of mutable state spaces and precisely describing how variables are manipulated in a program is a fundamental problem in compositional verification. Though we can make use of the embedded abstract syntax of a program for such analysis, this runs contrary to the shallow-embedding approach, and hampers efficient proof automation. On the other hand, lenses and prisms provide an elegant algebraic foundation for modelling state, which provide sufficient structure to provide meta-logical program analysis, but without requiring a deep embedding. Nevertheless lenses, as complex algebraic objects, cannot easily be combined, complemented, or collected in sets. In this paper we contribute an accompanying algebraic structure called the scene, which allows us to characterise the set of variables, or coordinates, in a state space. Scenes intuitively correspond to sets of lenses, but like lenses they are purely semantic algebraic objects. We demonstrate that scenes provide us with sufficient structure to characterise the lens-based meta-logical properties, like independence and equivalence. Moreover, we introduce the notion of a scene space, analogous to a vector space, which allows us to recover a set-like algebraic structure. Finally, we show how scenes allow us to characterise the free and bound variables of expressions and programs, without any need for syntax, and demonstrate their use for reasoning about programs by deriving reasoning principles for the parallel composition operator.

0.34

From Language to Task Maps: Compiling Semantic Relations While Preserving Task-Relevant Freedom

cs.RO ·2026-09-28 ·Jaegyun Park, Jingwang Lee, Jungsoo Lee, Soonwoong Hwang, Wansoo Kim
similarity 0.56
Abstract

Natural-language manipulation instructions specify qualitative relations, whereas continuous controllers require state-evaluable task quantities, differentials, and completion conditions. Because a qualitative relation generally leaves part of the relative configuration unspecified, expanding it into a complete pose can introduce unintended constraints. We present a typed semantic-to-geometric interface in which language specifies entities, relations, and phases, while each relation indexes a registered specification of its task-relevant distinctions and preserved freedoms. A robot-side compiler grounds these specifications, constructs relation-specific task maps and consistent differentials using conformal geometric algebra, and composes the resulting policies through RMPflow. To evaluate the division of responsibility between the language model and the compiler, we compared a Semantic Topology interface with one that additionally requires relation-specific geometric specifications over 60 instructions. Both produced correct shared semantic content in 41/60 cases, but critical errors under their respective interface requirements occurred in 19/60 and 58/60 cases. Across 64 grounded evaluations spanning eight geometric relation forms, the task maps preserved registered null directions and responded to relation-relevant perturbations; analytic directional derivatives agreed with finite differences, and Jacobian ranks matched the registered dimensions. In three closed-loop ablations using a simulated Franka Emika Panda in MuJoCo, fixing a relation-preserved coordinate increased median terminal progress error by 20.24--71.00~mm while the retained relation errors remained within their evaluation bounds. These results support compiling relation-visible geometry and preserved freedom together into composable continuous objectives.

0.20

An Algebra of Transformers

cs.LO cs.AI ·2026-10-27 ·Yong Wang, Zhiyan Wang, Hexiao Kang
similarity 0.56
Abstract

On the theoretic analyses on transforms, they mainly focus on the computability analysis, such the Turing-completeness of unbounded precision transformers, the advantage of parallelizability of unbounded precision transformers and the limitations of bounded precision transformers. This paper give transformers an algebra for reasoning, which relies heavily on the functional decomposition results of transformers. This algebra uses functional decompositions as atomic actions, includes sequential composition and parallel composition, recursion for feedback and abstraction for hidden layers. As we know, it is the first attempt to model transformers logically and can be used to verify the correctness of transformer based applications.

0.23

Pyramidal Columns Acting as Attention Heads

cs.AI q-bio.NCcs.NE ·2026-11-11 ·Fabrizia Giulia Garavaglia, Marco Giunti
similarity 0.55
Abstract · v1: main text (20 pp., 7 figs.) and supplementary materials (12 figures); v2: Fig. S2d corrected

Can the functional architecture of a Transformer attention head be given a biological construction? More specifically, could a suitable group of pyramidal columns in posterior temporal language regions (PTLRs) constitute the biological construction of a neuromorphic mechanical realization of an attention head, under a mathematical instantiation that need not coincide with its standard Transformer instantiation? This paper investigates this hypothesis by examining possible correspondences between the functional organization of attention heads and neurophysiological mechanisms operating within and across pyramidal columns involved in human language processing. Our analysis builds on a mechanical-structural description of Transformer attention heads as systems of simple neural networks linked through output-input and output-weight interconnections. We examine the functional organization of an attention head and the input-dependent transformations it produces, and ask how the corresponding processing relations could be constructed in biological neural tissue. We then identify candidate neural mechanisms of signal transmission and modulation within and across pyramidal columns that may jointly support such a construction. On this basis, we propose that a suitably organized group of pyramidal columns in PTLRs could constitute a biological construction of a neuromorphic mechanical realization of an attention head. Whether the required functional organization actually exists in PTLRs remains an open empirical question. The hypothesis does not require the biological system to reproduce the standard mathematical instantiation of Transformer attention: the same functional architecture may be mechanically realized and mathematically instantiated in a different way, consistent with its biological construction.

0.37

Arbitrary Functors as Modalities in a Linear Calculus

cs.PL ·2026-10-16 ·Jean-Philippe Bernardy, Andreas Abel
similarity 0.55
Abstract

We study modalities in the linear lambda calculus, by interpreting them as endofunctors in monoidal closed categories. We support functors that do not distribute over products, including (co)monads. We also support arbitrary natural transformations as conversion between modalities. We provide a generic categorical semantics, which we then specialise to a sound and complete resource semantics. We use this resource semantics to derive normalisation by evaluation. Along the way, we describe several applications of such models. This work aims at providing a foundation for future programming languages with modalities. The paper is backed by a mechanisation in Agda.

0.15

CIRT: Calculus of Inductive Refinement Types

cs.PL ·2026-11-16 ·Alessio Ferrarini, Niki Vazou, G. A. Kavvos
publishedhot direction similarity 0.54
Abstract · Extended version of the POPL 2027 paper

Refinement types are a powerful mechanism for statically verifying properties of programs. They have been successfully integrated into practical languages such as Haskell, Scala, and Rust. However, their metatheory is not yet fully understood. In this paper we present the first semantic model for a refinement type system that supports the full feature combination of subtyping, SMT-style equality, impredicative polymorphism, and (stratified) inductive types. Interactions between these features have led to inconsistencies in the past, and existing formalizations of refinement type systems omit at least one of them. We present a realizability model based on partial equivalence relations (PERs) over a Scott domain, which overcomes these obstacles. We use our model to prove the consistency of a core refinement type system and to give a semantic account of the annotation-independence property of refinement types. Our semantics uses two interpretations: a refined one, which interprets types and their refinements as PERs; and an unrefined one, consisting of complete uniform PERs with a bottom element (CUPERs), which models computational behaviour independently of refinements. We extend the model to positive and stratified inductive types, showing that both are consistent in the presence of impredicativity.

0.51