CS Paper Radar

The Asymptotics of Language Model Alignment with Memory

Haricharan Balasundaram, V. Arvind Rameshwar

cs.CL cs.IT ·submitted 2026-10-01 15:04 UTC · v1

Abstract

Language model (LM) alignment broadly aims to perturb a given LM $Q$ into an aligned LM $q$ such that i) the outputs produced by $q$ and $Q$ are 'close' in probability, ii) $q$ has a higher expected reward than $Q$. Two common techniques for LM alignment are: KL-constrained RL, which requires knowledge of the LM distribution and is computationally expensive, and the best-of-$n$ algorithm, which requires only sampling from the LM. The work of Yang et al. established asymptotic closeness between the distributions produced by the two alignment methods for an $m$--length i.i.d. token sequence output by the LM, in the limit as $m$ increases to infinity. However, the i.i.d. assumption is not representative of practical LMs, whose output sequences often have memory. In this paper, we extend the asymptotic closeness result to the case when the $m$--length token sequence outputted by the LM is Markovian. Further, for finite-length output sequences -- particularly, when $m=1$ -- we provide a complete characterization of LM distributions and reward functions for which the KL-divergence between the distributions produced by the two alignment methods is zero -- a question first posed in Yang et al.

Closest papers

Nearest neighbours by meaning across the whole index.

Margin Dynamics for Large Language Model Alignment

cs.LG cs.AI ·2026-11-16 ·Xingzi Xu, Mehmet Saygin Seyfioglu, Karim Bouyarmane
theory similarity 0.63
Abstract

Practitioners choose among LLM alignment methods largely by trial and error. We provide a theoretical foundation: each pairwise method defines a vector field on the probability simplex that governs how the model redistributes mass between preferred and dispreferred completions. Projecting onto a single preferred/dispreferred pair reduces this to a one-dimensional margin ODE with a closed-form solution. These solutions reveal that DPO margins grow without bound (logarithmically as $O(\log t)$ in the gradient-flow limit) while IPO margins converge to a finite $1/(2τ)$; that label noise induces a qualitative phase transition in DPO (unbounded $\to$ bounded) but affects IPO only quantitatively; and that gradient concentration under asymmetric weighting governs trainability at scale. We confirm all three predictions across five model families spanning four benchmarks. The closed-form solutions also enable principled method design: we prove that adding any label smoothing $\varepsilon > 0$ to SimPO creates a finite margin attractor at $Δ^* = β^{-1}\log((1-\varepsilon)/\varepsilon)$, while $\varepsilon = 0$ (standard SimPO) has no attractor. We test this across three models (8B-9B) and confirm the prediction: the theory-derived configuration (TPO-S, $\varepsilon = 0.05$) is competitive with the strongest baselines, attaining the highest mean IFEval score among the compared methods on all three, validating that the predicted finite attractor is a usable operating point rather than proposing a new state-of-the-art loss.

0.21

The Hardness of Estimating Cross-Entropy Risk for Language Models

cs.LG stat.ML ·2026-08-16 ·Hanti Lin
theory similarity 0.61
Abstract · Substantially revised and expanded version under a new title. Retains the main impossibility results of v1 and adds a new positive theorem c…

Language models, once pretrained, are routinely assessed by the holdout method, which estimates their per-token cross-entropy risk---a quantity that may be finite or infinite. We prove possibility and impossibility theorems that characterize the hardness of this estimation problem. The estimand depends on two objects: the unknown data distribution $p$ and the distribution $q$ induced by the language model under study. Our ignorance of $p$ is empirical, whereas our ignorance of $q$, or at least of its tail, is mathematical; so the parameter space {\em should} range over pairs $(p,q)$---a product space---to fully capture our ignorance. {\em Negative results}: no estimator is pointwise consistent, even when the parameter space is restricted to full-support models and to data distributions whose expected text length is below a fixed bound; worse, every estimator fails on a dense set of pairs. {\em Positive results}: the holdout estimator becomes pointwise consistent when the models are further restricted to Transformers or, architecture-neutrally, to full-support models with a finite context window; and, where no such design is in place, it still consistently estimates the risk capped at any fixed threshold, which suffices for screening candidate models in practice. {\em Lesson}: designs such as the Transformer architecture and finite context windows, although adopted for computational or engineering reasons, pay a {\em statistical dividend}: they suffice to make pointwise consistency possible---a dividend visible only in how they turn a negative result into positive ones.

0.04

Cross-Lingual Representation Alignment by Token-Level Optimal Transport in a Language-Agnostic Space

cs.CL ·2026-09-06 ·Taisei Yamamoto, Ryoma Kumon, Danushka Bollegala, Hitomi Yanaka
top venuecode/data similarity 0.60
Abstract · Accepted to EMNLP 2026 main

Cross-lingual alignment (CLA) aims to align the representations of large language models (LLMs) across languages, enabling cross-lingual transfer to improve multilingual capabilities. Previous CLA methods often ignore language-specific information encoded in representations and only consider sentence-level alignment, which may lead to suboptimal performance and input-output language mismatch. We propose CAROT (Cross-Lingual Alignment of Representations in a Language-Agnostic Space via Optimal Transport), which consists of two steps: identifying language-specific representations in LLMs' internal states and aligning language-agnostic representations across languages at the token level by optimal transport, while explicitly preserving language-specific representations. Inference-time steering experiments show that the representations computed by CAROT are effective alignment targets, improving multilingual performance by up to 11.2 points in accuracy while maintaining input-output language consistency. We further use the representations obtained by CAROT as training targets, internalizing the aligned representations. The trained models outperform existing CLA methods in 11 of 18 evaluation settings (3 models $\times$ 3 tasks $\times$ ID/OOD languages). Our work provides insights into what constitutes effective alignment targets for CLA in LLMs. Code is available at https://github.com/ynklab/CAROT

0.45

Recursive memory for prediction and generation

cs.IT stat.AP ·2026-11-10 ·Pengbin Feng, Chunlei Meng
theory similarity 0.59
Abstract

Recurrent and state-space language models compress the past into a state of fixed size. The state must answer questions about the future now, and it must remain useful as new tokens arrive, including tokens the model samples itself. We show that the second requirement can cost far more memory than the first. For a known hidden Markov source with positive transition probabilities, a state of $O(\log(1/\varepsilon))$ bits answers every question about the future to accuracy $\varepsilon$, however far ahead it looks, because the Bayesian filter forgets its rounding errors. Generating the future is different. When a model feeds each sampled token back into its state, the small errors in its next-token distributions add up, and $T$ tokens can require a state of order $\log(T/\varepsilon)$ bits. The lower bound comes from the KL chain rule: at every step, a model with $K$ states pays for approximating the true next-token distribution by one of only $K$ distributions. The argument applies to any source, including a language model continuing a prompt, and a small-ball estimate makes it tight for two-state sources. The extra $\log T$ disappears if the model keeps private randomness, or if error is budgeted per token, as in perplexity. Statistics of the recent past show the same gap between describing and maintaining. The number of ones among the last $n$ bits takes $\log n$ bits to write down. But if each bit is a noisy copy of the one $n$ steps earlier, tracking that count to a mean-square error $E^2$ well below its variance costs order $n/(1+E^2)+\log n$ bits. Information about each bit must be kept until the bit leaves the window, and a queue holding the counts of recent blocks keeps just enough of it.

0.17

Distortion of AI Alignment Revisited: RLHF is a Decent Utilitarian Aligner

cs.LG cs.GT ·2026-09-11 ·Kazusato Oko, Annie Ulichney, Nika Haghtalab, Han Bao
top venuetheoryhighly cited similarity 0.58
Abstract

While Reinforcement Learning from Human Feedback (RLHF) is the standard paradigm for aligning large language models with human preferences, its effectiveness in pluralistic settings has been called into question. Notably, recent work by Gölz et al. (2025) demonstrated that the \textit{distortion} -- defined as the multiplicative gap between the average user utility of the RLHF policy and the optimal average utility -- can scale exponentially with the Bradley-Terry temperature parameter $β$ when users have heterogeneous preferences. In this work, we present a fine-grained analysis of the distortion of RLHF with reward clipping and demonstrate that such exponential degradation is not a fundamental property of the algorithm but rather a consequence of distribution mismatch between the distribution generating preference data ($μ$) and the KL reference policy ($π_{\mathrm{ref}}$). To this end, we establish tight upper and lower bounds on the distortion of RLHF across multiple regimes of the KL regularization strength. We show that in a representative regime, under the Bradley-Terry model, the distortion is $\tildeΘ(βB + β)$, where $B$ is an upper bound on the log density ratio between $μ$ and $π_{\mathrm{ref}}$. In particular, when there is no distribution mismatch (i.e., $μ= π_{\mathrm{ref}}$), RLHF achieves the optimal distortion of $O(β)$ up to a constant. Our results suggest that, to reasonably maximize average utility with RLHF, it is preferable to use on-policy sampled preference data or to fine-tune before RLHF on data from a source close to $μ$.

0.72

Small-Space Streaming Hamming Approximation

cs.DS ·2026-11-18 ·Przemyslaw Uznanski
similarity 0.57
Abstract

For a preprocessed pattern of length $m$ and a streaming text, we give two algorithms that estimate the Hamming distance at every alignment to relative error $\varepsilon$. They use $\varepsilon^{-8/5}m^{2/5+o(1)}$ and $\varepsilon^{-1} m^{1/2+o(1)}$ words of space, respectively, including all retained pattern information. Each estimate is reported as soon as its window ends, and all estimates are simultaneously correct with high probability. The prior space bounds are $\widetilde{O}(\varepsilon^{-3/2}\sqrt{m})$, due to Chan et al. [CGK+20], and $\widetilde{O}((m/\varepsilon)^{2/3})$, a consequence of their results and those of Clifford, Kociumaka, and Porat [CKP18]. For $\varepsilon=Θ(m^{-a})$, the better of our two bounds improves on both prior space exponents for every fixed $0<a<1/2$. A Fourier matcher uses $\widetilde{O}(\varepsilon^{-2}(m/K)^2)$ words to estimate each distance $d$ within $\varepsilon(d+K)$, giving relative error at most $2\varepsilon$ for $d\ge K$. A threshold matcher based on random-prime residue refinements and the multi-stream dictionary matching algorithm of Golan, Kopelowitz, and Porat [GKP18] gives our second space bound directly. Combining it with the Fourier matcher gives the first. Both space bounds extend to $L_1$ matching over polynomially bounded integer symbols.

0.13

Five Architectures, One Shared Space Cross-Model Representational Alignment Without Weight Merging

cs.CL ·2026-10-24 ·Oladimeji Anthonio, Dimeji Olawuyi, Oloruntoba Ajayi, Temilola Aderemi
similarity 0.57
Abstract

Combining language models is usually done by averaging weights, which works only when the models share a common starting point. We ask whether five frozen, independently trained models with different internal designs (four transformers from four organizations and one state-space model) can be related through their activations alone, with no weight merging. Using permutation tests, an independent replication probe set, depth sweeps, pooling ablations and confound checks, we find statistically robust correspondence between how the five models organize the same text. It is strongest at each model's final layer and weaker for the state-space model, whose weakest pairing is still 35-43 times chance. We use this to build a shared space with Generalized Procrustes Analysis, in which no model is a fixed reference. At the final layer, mean held-out retrieval accuracy over the twenty ordered model pairs is 0.91 to 0.93 on two probe sets (chance 0.03), beating pairwise linear maps (0.82 to 0.85), but the space is worse than those maps in the middle layers. It transfers to ordinary English of unfamiliar grammatical form and fails on mathematical and logical notation. We then test whether the space supports a router that picks among the five models on gradeable tasks. Across four task types we find no case where routing beats always using the strongest model, and we report this as a negative result. A correctness signal that looked strong turned out to be category membership in disguise. All experiments ran on one laptop without a GPU.

0.16

PORT: Preference Optimization via Robust Token-Level Reweighting

cs.CL cs.AI ·2026-11-09 ·Ding Zhu, Xiukun Wei, Tian Xie, Zhihui Zhu, Xueru Zhang +1 more
theorycode/data similarity 0.57
Abstract · 10 pages, 4 figures, neurips 2026

Preference optimization has become a central approach for aligning large language models with human values, but its effectiveness depends heavily on the quality of preference annotations. In practice, preference data is often noisy due to annotation errors and ambiguity. Existing robust preference optimization methods primarily operate at the sequence level, implicitly treating entire responses as uniformly correct or incorrect. However, rejected responses may still contain informative reasoning steps, while preferred responses can include subtle errors. In this work, we propose \textbf{P}reference \textbf{O}ptimization via \textbf{R}obust \textbf{T}oken-level reweighting \textbf{(PORT)}, a fine-grained framework for robust alignment under noisy preferences. PORT performs token-level reweighting using the empirical cumulative distribution function (CDF) of token log-probabilities, yielding an efficient forward-pass-only proxy to gradient-norm penalization that selectively suppresses corrupted tokens without additional backward-pass computation. We provide theoretical analysis showing that PORT reduces the gradient bias from noisy preference labels by minimizing an upper bound on the bias term. Extensive experiments across diverse noise settings demonstrate that PORT consistently improves robustness and outperforms existing sequence-level baselines. The code is available at https://github.com/osu-srml/PORT

0.18