Author name cluster

Alexander Kozachinskiy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models

Hector Pasten
Felipe Urrutia
Hector Orellana
Cristian Buc Calderon
Cristobal Rojas
Alexander Kozachinskiy

Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existence of two phenomena in Transformers, namely isolation and continuity. Both of these phenomena hinder Transformers to learn even simple pattern sequences. Isolation expresses that any learnable sequence must be isolated from another learnable sequence, and hence some sequences cannot be learned by a single Transformer at the same time. Continuity entails that an attractor basin forms around a learned sequence, such that any sequence falling in that basin will collapse towards the learned sequence. Here, we mathematically prove these phenomena emerge in all Transformers that use compact positional encoding, and design rigorous experiments, demonstrating that the theoretical limitations we shed light on occur on the practical scale.

PDF Details

ICML Conference 2025 Conference Paper

Ehrenfeucht-Haussler Rank and Chain of Thought

Pablo Barceló
Alexander Kozachinskiy
Tomasz Steifer

The notion of rank of a Boolean function has been a cornerstone in PAC learning, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought (CoT) steps required by a single-layer Transformer with hard attention to compute $f$. Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that $\ell$-fold function composition necessitates exactly $\ell$ CoT steps. Furthermore, we analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.

Details

JAIR Journal 2025 Journal Article

On Computing Probabilistic Explanations for Decision Trees

Marcelo Arenas
Pablo Barcelo
Alexander Kozachinskiy
Miguel Romero
Bernardo Subercaseaux

Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the most studied cases is that of explaining the choices taken by decision trees, as they are traditionally deemed as one of the most interpretable classes of models. Recent work has focused on studying the computation of sufficient reasons, a kind of explanation in which given a decision tree T and an instance x, one explains the decision T (x) by providing a subset y of the features of x such that for any other instance z compatible with y, it holds that T (z) = T (x), intuitively meaning that the features in y are already enough to fully justify the classification of x by T. It has been argued, however, that sufficient reasons constitute a restrictive notion of explanation. For such a reason, the community has started to study their probabilistic counterpart, in which one requires that the probability of T (z) = T (x) must be at least some value δ ∈ (0, 1], where z is a random instance that is compatible with y. Our paper settles the computational complexity of δ-sufficient-reasons over decision trees, showing that both (1) finding δ-sufficient-reasons that are minimal in size, and (2) finding δ-sufficient-reasons that are minimal inclusion-wise, are computationally intractable. By doing this, we answer two open problems originally raised by Izza et al. (2021), and extend the hardness of explanations for Boolean circuits presented by Wäldchen et al. (2021) to the more restricted case of decision trees. Furthermore, we present sharp non-approximability results under a widely believed complexity hypothesis. On the positive side, we identify structural restrictions of decision trees that make the problem tractable.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Optimal Bounds for Dissatisfaction in Perpetual Voting

Alexander Kozachinskiy
Alexander Shen
Tomasz Steifer

In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior ---which we call 'bounded conflicts' condition---under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Strassen Attention, Split VC Dimension and Compositionality in Transformers

Alexander Kozachinskiy
Felipe Urrutia
Hector Orellana
Tomasz Steifer
Germán Pizarro
Matías Fuentes
Francisco Meza Vásquez
Cristian Buc Calderon

We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations for three tasks that require advanced reasoning. The first task, Match 3 (Sanford et al. , 2023), requires looking at all possible token triplets in an input sequence. The second and third tasks address compositionality-based reasoning: function composition (Peng et al. , 2024) and binary relations composition, respectively. We formally prove the inability of one-layer softmax Transformers to solve any of these tasks. To overcome these limitations, we introduce Strassen attention and prove that, equipped with this mechanism, a one-layer transformer can in principle solve all these tasks. Importantly, we show that it enjoys sub-cubic running-time complexity, making it more scalable than similar previously proposed mechanisms, such as higher-order attention (Sanford et al. , 2023). To complement our theoretical findings, we experimentally studied Strassen attention and compared it against standard (Vaswani et al, 2017), higher-order attention (Sanford et al. , 2023), and triangular attention (Bergen et al. 2021). Our results help to disentangle all these attention mechanisms, highlighting their strengths and limitations. In particular, Strassen attention outperforms standard attention significantly on all the tasks. Altogether, understanding the theoretical limitations can guide research towards scalable attention mechanisms that improve the reasoning abilities of Transformers.

PDF Details

CSL Conference 2024 Conference Paper

Energy Games over Totally Ordered Groups

Alexander Kozachinskiy

Kopczyński (ICALP 2006) conjectured that prefix-independent half-positional winning conditions are closed under finite unions. We refute this conjecture over finite arenas. For that, we introduce a new class of prefix-independent bi-positional winning conditions called energy conditions over totally ordered groups. We give an example of two such conditions whose union is not half-positional. We also conjecture that every prefix-independent bi-positional winning condition coincides with some energy condition over a totally ordered group on periodic sequences.

Details

ICLR Conference 2024 Conference Paper

Logical Languages Accepted by Transformer Encoders with Hard Attention

Pablo Barceló
Alexander Kozachinskiy
Anthony W. Lin
Vladimir V. Podolskii

We contribute to the study of formal languages that can be recognized by transformer encoders. We focus on two self-attention mechanisms: (1) UHAT (Unique Hard Attention Transformers) and (2) AHAT (Average Hard Attention Transformers). UHAT encoders are known to recognize only languages inside the circuit complexity class ${\sf AC}^0$, i.e., accepted by a family of poly-sized and depth-bounded boolean circuits with unbounded fan-ins. On the other hand, AHAT encoders can recognize languages outside ${\sf AC}^0$), but their expressive power still lies within the bigger circuit complexity class ${\sf TC}^0$, i.e., ${\sf AC}^0$-circuits extended by majority gates. We first show a negative result that there is an ${\sf AC}^0$-language that cannot be recognized by an UHAT encoder. On the positive side, we show that UHAT encoders can recognize a rich fragment of ${\sf AC}^0$-languages, namely, all languages definable in first-order logic with arbitrary unary numerical predicates. This logic, includes, for example, all regular languages from ${\sf AC}^0$. We then show that AHAT encoders can recognize all languages of our logic even when we enrich it with counting terms. Using these results, we obtain a characterization of which counting properties are expressible by UHAT and AHAT, in relation to regular languages.

Details

ICML Conference 2024 Conference Paper

On dimensionality of feature vectors in MPNNs

César Bravo
Alexander Kozachinskiy
Cristobal Rojas

We revisit the result of Morris et al. (AAAI’19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler–Leman (WL) isomorphism test. Morris et al. show their result with ReLU activation function and $O(n)$-dimensional feature vectors, where $n$ is the size of the graph. Recently, by introducing randomness into the architecture, Aamand et al. (NeurIPS’22) improved this bound to $O(\log n)$-dimensional feature vectors, although at the expense of guaranteeing perfect simulation only with high probability. In all these constructions, to guarantee equivalence to the WL test, the dimension of feature vectors in the MPNN has to increase with the size of the graphs. However, architectures used in practice have feature vectors of constant dimension. Thus, there is a gap between the guarantees provided by these results and the actual characteristics of architectures used in practice. In this paper we close this gap by showing that, for any non-polynomial analytic (like the sigmoid) activation function, to guarantee that MPNNs are equivalent to the WL test, feature vectors of dimension $d=1$ is all we need, independently of the size of the graphs. Our main technical insight is that for simulating multi-sets in the WL-test, it is enough to use linear independence of feature vectors over rationals instead of reals. Countability of the set of rationals together with nice properties of analytic functions allow us to carry out the simulation invariant over the iterations of the WL test without increasing the dimension of the feature vectors.

Details

NeurIPS Conference 2023 Conference Paper

Three Iterations of (d − 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points

Valentino Delle Rose
Alexander Kozachinskiy
Cristobal Rojas
Mircea Petrache
Pablo Barceló

The Weisfeiler-Lehman (WL) test is a fundamental iterative algorithm for checking the isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of Euclidean points represented by complete distance graphs, i. e. , when it can distinguish, up to isometry, any arbitrary such cloud. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and only three iterations of the test suffice. Our result is tight for $d = 2, 3$. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness.

PDF Details

Highlights Conference 2022 Conference Abstract

State Complexity of Chromatic Memory in Infinite-duration Games

Alexander Kozachinskiy

Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run, thereby preserving many of the desirable algorithmic properties of finite automata. Here, we study the extension of the classical framework onto infinite inputs, as well as their history-deterministic variant and the problem of solving games with winning conditions expressed by Parikh automata. We define reachability, safety, Büchi, and co-Büchi Parikh automata on infinite words and show that safety and co-Büchi ones have an undecidable emptiness problem. On the other hand, Parikh automata with reachability or Büchi acceptance have a decidable emptiness problem, implying, in particular that in this setting Büchi acceptance does not subsume safety, at least not effectively. History-deterministic automata allow a limited form of nondeterminism and are often well-suited for applications which classically call for deterministic automata, e. g. , solving games and composition. We show that history-deterministic Parikh automata are more expressive than deterministic ones, but less expressive than nondeterministic ones. However, they are not well-suited for games, as we prove that solving games is undecidable even for winning conditions given by deterministic Parikh automata on finite words. Furthermore, we determine the closure properties of history-deterministic Parikh automata and show that universality and regularity are undecidable for such automata.

Details

Highlights Conference 2021 Conference Abstract

One-to-Two-Player Lifting for Mildly Growing Memory

Alexander Kozachinskiy

We investigate so-called “one-to-two-player lifting” theorems for infinite-duration two-player games on graphs with zero-sum objectives. These theorems are concerned with questions of the following form. If that much memory is sufficient to play optimally in one-player games, then how much memory is needed to play optimally in two-player games? In 2005, Gimbert and Zielonka (CONCUR 2005) have shown that if no memory is needed in the one-player games, then the same holds for the two-player games. Building upon their work, Bouyer et al. ~(CONCUR 2020) have shown that if some constant amount of memory (independent of the size of a game graph) is sufficient in the one-player games, then exactly the same constant is sufficient in the two-player games. They also provide an example in which every one-player game requires only a finite amount of memory (now this amount depends on the size of a game) while some two-player game requires infinite memory. Our main result states the following. If the memory grows just a bit slower (in the one-player games) than in the example of Bouyer et al. , then in every two-player game it is sufficient to have finite memory. Thus, our work identifies the exact barrier for the one-to-two-player lifting theorems in a context of finite-memory strategies.

Details

SODA Conference 2021 Conference Paper

Polyhedral Value Iteration for Discounted Games and Energy Games

Alexander Kozachinskiy

We present a deterministic algorithm, solving discounted games with n nodes in -time. For bipartite discounted games our algorithm runs in n O (1) ·2 n -time. Prior to our work no deterministic algorithm running in time 2 o ( n log n ) regardless of the discount factor was known. We call our approach polyhedral value iteration. We rely on a well-known fact that the values of a discounted game can be found from the so-called optimality equations. In the algorithm we consider a polyhedron obtained by relaxing optimality equations. We iterate points on the border of this polyhedron by moving each time along a carefully chosen shift as far as possible. This continues until the current point satisfies optimality equations. Our approach is heavily inspired by a recent algorithm of Dorfman et al. (ICALP 2019) for energy games. For completeness, we present their algorithm in terms of polyhedral value iteration. Our exposition, unlike the original algorithm, does not require edge weights to be integers and works for arbitrary real weights.

Details

Highlights Conference 2020 Conference Abstract

Positionality and strategy improvement for continuous payoffs

Alexander Kozachinskiy

A fundamental question for two-player antagonistic games on finite directed graphs is to characterize positional payoffs, i. e. , payoffs that always have optimal positional strategies. We investigate this question in a special case of continuous payoffs, both for deterministic and for stochastic games. A well-studied example of a continuous positional payoff is the (multi)discounted payoff. We show that in case of stochastic games the multidiscounted payoff is, in fact, the only continuous payoff which is positional. In contrast, the class of continuous deterministically positional payoffs turns out to be wider. Thus, we answer negatively to a question of Gimbert (STACS 2007), who conjectured that all deterministically positional payoffs are stochastically positional. We then obtain a simple characterization of the class of deterministically positional continuous payoffs. Namely, we introduce a property that we call prefix-monotonocity and show that this property is necessary and sufficient for a continuous payoff to be (deterministically) positional. The machinery of our proofs has some further consequences. Namely, it turns out that any game with a continuous positional payoff can be solved by strategy improvement (in fact, we use strategy improvement in the proof of sufficiency of prefix-monotonocity). From that we also derive that any such game can formulated as an LP-type problem and thus can be solved in randomized sub-exponential time. Finally, we address the question of showing strong bounds on strategy improvement for continuous payoffs. We generalize edge eliminating technique which was originally developed to show strong bounds on strategy improvement for the multidiscounted payoff. We show that some results obtained with this technique can be applied to other continuous payoffs too, including one that we call non-linear discounted payoff.

PDF Details

MFCS Conference 2018 Conference Paper

From Expanders to Hitting Distributions and Simulation Theorems

Alexander Kozachinskiy

In this paper we explore hitting distributions, a notion that arose recently in the context of deterministic "query-to-communication" simulation theorems. We show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs. In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has k bits on input, it admits a simulation theorem for all outer function of arity roughly 2^(k/2) or less (the same was also known for k-bit Inner Product). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time 2^O(k), i. e. in time polynomial in size of gadget's matrix. We also obtain two results showing that with current technique no better trade-off between the arity of outer function and the size of gadget can be achieved. Namely, we observe that no gadget can have hitting distributions with significantly better parameters than Inner Product or our new affine plane gadget. We also show that Thickness Lemma, a place which causes restrictions on the arity of outer functions in proofs of simulation theorems, is unimprovable.

Details

MFCS Conference 2018 Conference Paper

One-Sided Error Communication Complexity of Gap Hamming Distance

Egor Klenin
Alexander Kozachinskiy

Assume that Alice has a binary string x and Bob a binary string y, both strings are of length n. Their goal is to output 0, if x and y are at least L-close in Hamming distance, and output 1, if x and y are at least U-far in Hamming distance, where L < U are some integer parameters known to both parties. If the Hamming distance between x and y lies in the interval (L, U), they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least U. In this paper we determine this complexity up to factors logarithmic in L. The protocol we construct for the upper bound is simultaneous.

Details