Improving Language Identification for Code-Switched Utterances with Integer Linear Programming

AI summary

Overview

Research area: Natural language processing — language identification (LID) for code-switched text, combining a FastText-based LID backbone with combinatorial optimization (Integer Linear Programming).

Technical level: Advanced. The paper assumes familiarity with FastText classifiers, softmax posteriors, greedy algorithms, and ILP modeling (binary variables, objective functions, constraints).

One-sentence scope: The paper diagnoses a weakness in MaskLID (a training-free, state-of-the-art code-switching LID method), rebuilds its backbone LID with word-level training data, and reformulates its greedy assignment procedure as an Integer Linear Program that is evaluated on eight code-switched language pairs and monolingual data in 10 languages.

What This Paper Is About

Language identification tools usually classify a whole sentence as one language, so they fail on intra-sentential code-switching, where two languages appear inside the same sentence. The paper starts from MaskLID, a training-free post-processing layer that turns any LID into a code-switching LID for arbitrary language combinations, and shows that MaskLID's word-level language scores — which it uses to decide which words to mask — are unreliable. The goal is to fix those word-level scores with a new backbone LID and to replace MaskLID's greedy masking loop with an explicit Integer Linear Program, yielding better global language assignments and much higher exact-match accuracy on code-switched benchmarks.

Key Contributions

1. Diagnosis and repair of MaskLID's word-level weakness. The authors show that MaskLID relies on word-level language association scores that are near-zero for the correct label in most cases, and they build LiteLID-v2, a FastText-based LID trained on 125 labels using full sentences plus single-word instances split from those sentences, to supply more reliable word-level probabilities.
2. An ILP reformulation of the assignment problem. The language assignment performed greedily by MaskLID is recast as an Integer Linear Program with an explicit objective (Equation 2) and a set of interpretable constraints on code-switched utterances, allowing the optimizer to find better global solutions.
3. A library of constraints and three reference configurations. Beyond the core constraints C1 (at most one language per word) and C2 (at most K languages per sentence), the paper adds a language-ranking mechanism with weights α and a penalty P, plus constraints C3 (minimum length τ in characters), C4 and C5 (top-M variants) and C6 (at most S language changes), and selects CS, MONO and AVG configurations.
4. Empirical validation across 10 languages and released code. Experiments on Turkish-English, Basque-Spanish, Hindi-English, Nepali-English, Turkish-German, Spanish-English, Indonesian-English and Wolof-French, with monolingual data from Flores+, show large gains; the code and data are released at github.com/jradola/ILP4LID.

Main Findings

• Word-level scores in GlotLID are largely unusable for masking. On a subset of FLORES sentences, GlotLID assigns a mean probability of 0.98 to the gold label at sentence level but only 0.31 at word level. LiteLID-v2 raises the word-level mean to 0.50 (sentence-level 0.96).
• A word-trained backbone improves short-text LID. LiteLID-v2, trained on sentences and words, outperforms GlotLID on small segments by 0.14 absolute points on sequences of length 6-10 (measured in F1 as a function of input length in characters). LiteLID-v1, trained only on words, is outperformed by LiteLID-v2.
• Replacing the backbone strongly improves MaskLID. On the development set, LiteLID-v2 + MaskLID with τ=5 reaches 0.39 Exact Match (EM) on code-switched data versus 0.31 for GlotLID + MaskLID, and 0.96 EM versus 0.69 on monolingual data. On the test set, the backbone change alone yields a +0.13 absolute increase in EM.
• The ILP optimizer adds further gains, especially on code-switched data. On the test set, the AVG configuration reaches 0.54 EM / 0.81 F1 on code-switched data (versus 0.39 EM / 0.78 F1 for LiteLID-v2 + MaskLID at τ=5), 0.88 EM on monolingual data, and 0.71 EM / 0.89 F1 overall. The combination of both improvements raises average EM from 0.54 to 0.71.
• Improvements are statistically significant. McNemar's test at α=0.05 gives p-values of 1.3e-302 (AVG), 1.3e-18 (MONO) and 0.0498 (CS); the CS difference is described as borderline significant.
• Gains are large for specific language pairs. Per-language results show EM increases up to +0.44 for Turkish-English and +0.35 for Nepali-English, part of which comes from the new backbone and part from the improved optimizer (e.g., for Turkish-English and Turkish-German).
• Different configurations trade off code-switched and monolingual accuracy. The CS configuration achieves 0.99 recall on monolingual data but only 0.04 EM, because with only C1 and C2 it predicts two languages almost always (e.g., monolingual English labeled {eng, nld} or {eng, fra}; monolingual Spanish labeled {spa, por}). The MONO configuration has high precision (0.96 average on code-switched data) but unsatisfactory recall (0.69), typically identifying only one of the two correct languages. The AVG configuration is reported as the best trade-off.
• The ILP assigns far more words. MaskLID leaves 23% of test words without a language assignment, whereas ILP4LID (AVG) assigns 97% of test words, giving a recall increase of +0.1 on the code-switched test set.
• Word-level evaluation confirms the same pattern. Macro-averaged over pairs with word-level gold labels, ILP4LID (CS) obtains precision 0.92 / recall 0.84 / F1 0.88 with 1.1% unassigned words, versus MaskLID (τ=5) precision 0.94 / recall 0.73 / F1 0.82 with 18.3% unassigned words. MaskLID's abstention maximizes precision but hurts recall and F1.
• The ILP is slower but GPU-free. On an Intel Core i5 desktop with 40GB RAM, the detector takes about 13 s (CS configuration) and 25 s (AVG and MONO) to process 80 sentences of around 80 characters, roughly a x10 increase over MaskLID for short segments (<50 characters) and x20 for longer ones. Runtime grows linearly with the number of language labels L.
• Very short, noisy social media text remains the hardest case. Examples such as "auuuuuuuuush jajaja asi se habla lmao", labeled Spanish-English in LinCE, illustrate the remaining difficulty.

Methodology in Plain English

MaskLID works by a loop: predict the most likely language for the whole sentence, check each word individually, and if that sentence language is among the M most likely languages for a word, assign the word to it and remove it from the text. The loop repeats on the shrinking remainder until what is left is shorter than a threshold τ, and the set of languages found along the way is returned.

The authors first tested the assumption behind this loop — that per-word LID scores can be trusted. They found they cannot: standard LIDs such as GlotLID are trained on sentences, so their per-word outputs are close to meaningless, with the correct label often receiving near-zero probability. Their fix was to train new FastText models (LiteLID) on 125 Latin-script labels, mixing whole sentences with isolated words taken from them, so that the model is competent both at sentence level (where it is tested) and at word level (where MaskLID uses it). LiteLID-v2, trained on sentences plus single words, is the variant selected.

Second, they rewrote the assignment step as an optimization problem with binary variables: y(l,t) = 1 if word t is assigned to language l, and u(l) = 1 if language l is used at all. The objective rewards assigning words to languages with high scores; constraints forbid assigning more than one language to a word and cap the number of languages per sentence. They then extended the objective with a penalty for each predicted language and weights α that order languages by their global score, and added optional constraints: a minimum character length τ before a language can be identified (C3), top-M restrictions on which languages a word may or may not take (C4, C5), and a cap S on the total number of language changes (C6). Three configurations were selected on development data — CS (core objective, C1+C2), MONO (α₁=1, α₂=0.7, P=20, C1, C2, C3 with τ=10, C5 with M=10) and AVG (α₁=1, α₂=0.75, P=15, C1, C2, C3 with τ=5, C5 with M=10) — then run once on the test set.

For evaluation, the authors balanced code-switched corpora (Turkish-English, Turkish-German, Basque-Spanish, Hindi-English, Nepali-English, Spanish-English, Indonesian-English, Wolof-French) with monolingual data, taking 500 shortest sentences per language from Flores+ and romanizing Hindi and Nepali with the uroman module. Development data consisted of 100 sentences randomly selected from five code-switched corpora plus 500 monolingual sentences (72 sentences per language for Basque, Turkish and Spanish; 71 for Hindi, Nepali, English and German); the remaining data was kept for testing. Sentences shorter than 20 or longer than 200 characters (excluding whitespace) were filtered out, along with emojis, URLs, @usernames, quotation marks, filler tokens starting with "%" and language tags. The main metric is exact match (EM) over the predicted language set, complemented by precision, recall and F1, macro-averaged across languages or pairs.

Why This Matters

Impact on research. The paper shows that the bottleneck of a widely used training-free code-switching LID is not its overall design but a hidden dependency on unreliable word-level probabilities, and that replacing a greedy loop with an explicit ILP yields measurable gains. It provides a constraint-based, interpretable framework that other researchers can extend, and it makes a case for training LIDs whose posteriors are usable at the word level as well as the sentence level.

Real-world applications (as supported by the paper's framing):

• Multilingual data collection and filtering pipelines, where LID tools operate in the early stages of building web-scale multilingual corpora and where low-resource languages can otherwise be absorbed into dominant languages.
• Building training data for large language models, since code-switched text is described as underrepresented in LLM training data.
• Processing informal social media content, where intra-sentential code-switching is described as particularly widespread.
• Supporting minority and low-resource language technologies, which the authors highlight as especially dependent on high-precision LIDs.

Industry relevance. The approach requires no training for the code-switching layer itself, works with arbitrary language combinations (with a FastText-based model such as GlotLID covering 2000+ languages, MaskLID readily identifies more than 4M combinations), needs no GPU, and can be distributed across CPU cores, which suits large-scale production filtering. The cost is runtime: the ILP is roughly 10x to 20x slower than MaskLID, and the authors note that preselecting the candidate language list to reduce L would directly cut runtime. They ran the ILP with Gurobi version 13 (free academic licences) and note the code can run with any open-source tool supported by the Pyomo framework, such as HiGHS.

Future Directions

• Better-calibrated posteriors and confidence scores. The authors state they will continue exploring the trade-off between word-level and sentence-level predictions, training LIDs with better calibrated posterior probabilities — something both MaskLID and ILP4LID require — and reporting model confidence scores.
• Broader language coverage. Extending to more languages is proposed, especially languages normally written in non-Latin scripts that can be transliterated on social media; the Hindi and Nepali work is presented as a first step, facilitated by a regular romanization process.
• Harder romanization and script-mixing settings. The limitations section raises code-switched data with less standard romanization, such as Arabizi for Arabic-French or Arabic-English, as a more challenging case because high-quality LIDs for such mixed text are difficult to find.
• Faster ILP-based CS LID. Optimizing the model to speed up code-switching LID with the ILP remains an explicit goal, given the linear dependence of runtime on the number of language labels.

Open questions the paper also surfaces: how to handle more than two languages per utterance, highly ambiguous words (punctuation, numbers, proper nouns, loan words), and intra-word code-switching, where a multi-label approach is suggested as a possible alternative.

Target Audience

Researchers and practitioners in multilingual NLP who work on language identification, data filtering for large-scale corpora, or code-switched and informal text processing. It will be most useful to readers already comfortable with FastText classification and with combinatorial optimization or ILP solvers, and to engineers deploying LID at scale who need to weigh accuracy against runtime. Readers interested in low-resource and minority language technology will also find the empirical

Authors’ abstract

Automatic identification of code-switched (CS) utterances remains a challenge for language identification (LID) systems, causing such texts to be underrepresented in the training data of Large Language Models. In this paper, we revisit MaskLID, a state-of-the art approach for CS identification, which requires no training and detects arbitrary language combinations. We make three main contributions: (a) we reveal, and address, a major issue of MaskLID: its overreliance on word-level language association scores; (b) we reformulate the underlying optimization algorithm as an Integer Linear Program, enabling us to experiment with a large set of clear and interpretable constraints; (c) each of these improvements vastly improves the baseline system, as we illustrate in experiments involving 10~diverse languages, where we observe a strong boost in performance on CS benchmarks. We release our code and data for reproducibility.