Transduced language models (TLMs) combine a pretrained source language model with a finite‑state transducer to produce a language model over target strings. The paper introduces an unbiased stochastic estimator that resamples source prefixes without replacement and reweights them, allowing accurate estimation of target prefix probabilities while reducing computation compared to threshold‑pruned beam summing. Experiments on encyclopedic text, DNA, and DNA‑to‑amino‑acid transduction show improved compute–variance trade‑offs and significant runtime reductions, and the method also lowers estimated corpus surprisal in a reading‑time analysis without altering its conclusions.
By V\'esteinn Sn{\ae}bjarnarson, Samuel Kiegeland, Manuel de Prada Corral, Ryan Cotterell, Tim Vieira
arXiv:2607. 24192v1 Announce Type: cross Abstract: We study the problem of lossless compression of source code, motivated by the storage demands of large-scale software archives, such as Software Heritage (https://www.
By Angelo Nardone, Paolo Ferragina
The paper introduces a new complexity measure, based on a restricted class of "layered zipline programs," which is weaker than the previously defined Arithmetic Repetition Complexity (ARC). This measure allows for a prediction algorithm that operates in quasilinear time and polylogarithmic space on highly-structured sequences, offering a more efficient solution at the cost of reduced expressivity compared to ARC. The work highlights a tradeoff between algorithmic efficiency and the breadth of sequences that can be effectively predicted.
By Vanessa Kosoy
arXiv:2608. 01320v1 Announce Type: cross Abstract: Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples.
By Ziyi Cai, Shuangping Li, Yiheng Shen, Kangning Wang, Peng Zhang
SimLens is a training‑free decoder that improves early‑layer predictions in large language models by keeping only the start token and a candidate answer token and performing a lightweight continuation through the remaining layers. It outperforms direct linear readouts, yielding higher accuracy on tasks such as ARC, BoolQ, and HeadQA with LLaMA‑7B and Vicuna‑7B. The method is extended to Linear SimLens for confidence estimation and combined into SimExit, a hybrid early‑exit mechanism that achieves significant speedups while maintaining accuracy.
By Ming Ma, Bowen Zheng, Zhongqiao Lin, Tianming Yang
arXiv:2606. 29203v1 Announce Type: new Abstract: We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.
By Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan
arXiv:2607. 18260v1 Announce Type: new Abstract: We introduce FindStatBench, an execution benchmark for evaluating large language models on combinatorial code synthesis.
By Soham Dan
arXiv:2601.05280v4 Announce Type: replace-cross
Abstract: On the one hand, the question of whether Large Language Models (LLMs) are Solomonoff induction estimators has become an explicit question at...
By Hector Zenil, Abicumaran Uthamacumaran, Luan Ozelim
The paper argues that Large Language Models (LLMs) do not function as Solomonoff induction estimators because their training objectives—cross‑entropy, negative log‑likelihood, and next‑token prediction—optimize fit to a supplied conditional distribution rather than a program‑weighted universal mixture. It further contends that additional computation alone does not transform these models into optimal predictors without external hyper‑parameter or architectural changes. The authors suggest that neurosymbolic machine learning, exemplified by models such as Fable and Astra, represents a shift toward symbolic model synthesis, moving beyond purely statistical LLMs.
By Hector Zenil, Abicumaran Uthamacumaran, Luan Ozelim
The paper introduces F-ICL, a benchmark that measures in‑context algorithmic reasoning in language models by exhaustively enumerating 86 million valid programs of length ≤13 on a Turing‑complete machine and computing the exact posterior under a bounded Levin–Solomonoff prior. Unlike typical benchmarks, F‑ICL provides a distributional reference rather than just answers, allowing the evaluation of models’ inductive priors. Across 105 configurations of models ranging from 0.8 B to 675 B parameters, models achieve up to 92 % accuracy, yet many still deviate from the Bayes‑optimal reference, and the study derives theoretical bounds on cumulative loss for predictors with positive prior weight on the reference.
By Luan Ozelim, Hector Zenil
The paper introduces a new framework for adaptive parallel sampling of discrete vectors, where a deterministic policy reveals coordinates round‑by‑round based on previously observed values and samples the remaining coordinates from their exact conditional marginals. The authors prove an exact identity linking the forward Kullback‑Leibler divergence of any policy to the expected conditional total correlation accumulated during the sampling process, establishing conditional total correlation as the precise information cost of within‑round parallelism. Using this identity, they derive zero‑error schedules for finite‑order Markov chains, characterize the serial depth of Bernoulli walks, and demonstrate separations between different reveal orders, permutation strategies, and string structures, thereby revealing how conditional dependence governs parallelizability.
whyItMatters":"The results provide a principled, information‑theoretic measure of parallel sampling efficiency that can guide the design of decoding rules for masked diffusion models and other generative systems."
By Chuling Wen, Weijie Liang, Jian Lu
arXiv:2609.08851v1 Announce Type: new
Abstract: Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particul...
By Georg Zetzsche, Hongjian Jiang, Andy Yang, Pascal Bergstr\"a{\ss}er, Marco S\"alzer, David Chiang, Anthony W. Lin