Research map / Large language models / Language, safety and interpretability

Agnostic Language Identification and Generation

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Statistical frameworks for LLM evaluation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Relaxes realizability in language identification and generation, proposing agnostic objectives, deriving identification rates that depend on attaining the infimum of out-of-language mass, and generation lower bounds plus exponential rates for well-behaved distributions.

Problem

Language identification and generation from i.i.d. positive examples are studied only under realizability (data supported on a language in the collection); the agnostic setting where the distribution's support may lie outside the collection has lacked statistical rates and suitable objectives.

Approach

Replace the realizable error with excess-error objectives relative to the best language in the collection (identification) and with error against supp(D) (generation); show identification achieves near-exponential rates iff the infimum of out-of-language mass is attained within the collection, and generation achieves exponential rates for finite collections when some language is contained in supp(

Key results

• Identification: for any countable collection where the infimum of out-of-language mass is attained, an algorithm achieves excess error e^{-g(n)} for any g(n)=o(n), with matching lower bound of order e^{-n}.
• Identification: there exists a countable collection and distributions for which no language attains the infimum, forcing arbitrarily slow rates R(n)=o(1) for infinitely many n.
• Generation: for any algorithm there is a distribution with limsup error at least 1-epsilon, showing no free lunch without further assumptions; for finite collections with a language contained in supp(D), an algorithm achieves error at most c*exp(-C*n), and a lower bound exp(-2n)/4 holds for infinite

Surprising findings

• Agnostic generation is intractable in general: for any algorithm some distribution forces error at least 1-epsilon, even with access to the full universe as a language.
• The natural sample-dependent benchmark for distribution-output generation changes with the input sample, and the size-dependent alternative benchmark shifts with n (best collection index grows roughly as log2 n).

Limitations

• Generation exponential-rate result is proven only for finite collections; extension to all countable collections is open.
• The generation objective may be too strong, as the general lower bound suggests; alternative objectives are not resolved.
• Purely theoretical; no experiments.

Experimental setup

Builds on: realizable language identification statistical rates online language generation in the limit agnostic online language generation

Closest papers by meaning

• On Union-Closedness of Language Generation (NeurIPS 2025 · similarity 0.87)
• Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.87)
• Language Generation in the Limit (NeurIPS 2024 · similarity 0.84)
• On the Query Complexity of Verifier-Assisted Language Generation (ICML 2025 · similarity 0.84)
• Representative Language Generation (ICML 2025 · similarity 0.84)
• GlotCC: An Open Broad-Coverage CommonCrawl Corpus and Pipeline for Minority Languages (NeurIPS 2024 · similarity 0.83)