Language Identification with Succinct Machine-Independent Traces

• URL: http://arxiv.org/abs/2607.12443v1
• Date: Tue, 14 Jul 2026 07:18:07 GMT
• Title: Language Identification with Succinct Machine-Independent Traces
• Abstract summary: We show how to define computational traces that enable identification in the limit.<n>We show how to define traces using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over.
• Score: 10.036312061637764
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages.

Related papers

• What Language is This? Ask Your Tokenizer [32.28976119949841]
  Language Identification (LID) is an important component of many multilingual natural language processing pipelines.<n>We introduce UniLID, a simple and efficient LID method based on the UnigramLM tokenization algorithm.<n>Our formulation is data- and compute-efficient, supports incremental addition of new languages without retraining existing models.
  arXiv  Detail & Related papers  (2026-02-19T18:58:39Z)
• LANGSAE EDITING: Improving Multilingual Information Retrieval via Post-hoc Language Identity Removal [34.73949500194166]
  multilingual embeddings encode language identity alongside semantics.<n>We propose LangSAE EDITING, a post-hoc sparse autoencoder trained on pooled embeddings.<n> Experiments across multiple languages show consistent improvements in ranking quality and cross-language coverage.
  arXiv  Detail & Related papers  (2026-01-08T09:36:41Z)
• Signs as Tokens: A Retrieval-Enhanced Multilingual Sign Language Generator [55.94334001112357]
  We introduce a multilingual sign language model, Signs as Tokens (SOKE), which can generate 3D sign avatars autoregressively from text inputs.<n>We propose a retrieval-enhanced SLG approach, which incorporates external sign dictionaries to provide accurate word-level signs.
  arXiv  Detail & Related papers  (2024-11-26T18:28:09Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Small Language Models Also Work With Small Vocabularies: Probing the Linguistic Abilities of Grapheme- and Phoneme-Based Baby Llamas [7.585433383340306]
  We show that tokenization-free, phoneme- and grapheme-based language models can achieve strong linguistic performance.<n>Our findings suggest a promising direction for creating more linguistically plausible language models.
  arXiv  Detail & Related papers  (2024-10-02T12:36:08Z)
• Egalitarian Language Representation in Language Models: It All Begins with Tokenizers [0.0]
  We show that not all tokenizers offer fair representation for complex script languages such as Tamil, Sinhala, and Hindi. We introduce an improvement to the Byte Pair algorithm by incorporating graphemes, which we term Grapheme Pair. Our experiments show that grapheme-based character extraction outperforms byte-level tokenizers for complex scripts.
  arXiv  Detail & Related papers  (2024-09-17T19:05:37Z)
• Soft Language Identification for Language-Agnostic Many-to-One End-to-End Speech Translation [40.0365339798752]
  Many-to-one end-to-end speech translation models can convert audio signals from different source languages into text in a target language. In some cases, the input language can be given or estimated. We accomplish this by introducing a simple and effective linear input network.
  arXiv  Detail & Related papers  (2024-06-12T00:00:39Z)
• Language Generation in the Limit [0.7787343335258782]
  We show that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning.
  arXiv  Detail & Related papers  (2024-04-10T05:53:25Z)
• Leveraging Adversarial Training in Self-Learning for Cross-Lingual Text Classification [52.69730591919885]
  We present a semi-supervised adversarial training process that minimizes the maximal loss for label-preserving input perturbations. We observe significant gains in effectiveness on document and intent classification for a diverse set of languages.
  arXiv  Detail & Related papers  (2020-07-29T19:38:35Z)
• Exploring Software Naturalness through Neural Language Models [56.1315223210742]
  The Software Naturalness hypothesis argues that programming languages can be understood through the same techniques used in natural language processing. We explore this hypothesis through the use of a pre-trained transformer-based language model to perform code analysis tasks.
  arXiv  Detail & Related papers  (2020-06-22T21:56:14Z)
• Limits of Detecting Text Generated by Large-Scale Language Models [65.46403462928319]
  Some consider large-scale language models that can generate long and coherent pieces of text as dangerous, since they may be used in misinformation campaigns. Here we formulate large-scale language model output detection as a hypothesis testing problem to classify text as genuine or generated.
  arXiv  Detail & Related papers  (2020-02-09T19:53:23Z)
• On the Importance of Word Order Information in Cross-lingual Sequence Labeling [80.65425412067464]
  Cross-lingual models that fit into the word order of the source language might fail to handle target languages. We investigate whether making models insensitive to the word order of the source language can improve the adaptation performance in target languages.
  arXiv  Detail & Related papers  (2020-01-30T03:35:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.