On noisy, dialect-heavy social media text, old-fashioned classifiers built on bags of word and character n-grams (short runs of words or letters, such as "un", "unb", "bel") still beat pretrained Transformers. On noisy Bangla sentiment, a support vector machine over word 1–3-grams and character 2–5-grams reaches 64.61 macro F1, while multilingual BERT reaches 52.79 (SentNoB). The obvious place to run such models is on cheap devices: phones in low-connectivity regions, or moderation filters on microcontrollers. The obstacle is memory. These models store one weight per distinct n-gram, which means hundreds of thousands of entries, and on a microcontroller simply cutting every n-gram out of each message and looking it up can cost more time than the classifier itself.
We propose to treat the n-gram front end as the thing to search. We keep a fixed Flash, RAM, and latency budget for the target chip. Under that budget, we jointly choose which n-gram tracks to compute (word unigrams, word bigrams, character n-grams of each length, with or without word-boundary markers), how many hash buckets each track gets, how wide and how many bits each track's embedding uses, and which frequently used entries live in fast RAM rather than Flash. The claim is that the best split of a few tens of kilobytes across tracks is uneven, differs by task and by chip, and cannot be recovered by the usual recipe of picking n-gram ranges by grid search and then compressing everything uniformly.
Core Claim
The claim is specific and falsifiable. Under Flash budgets of 32–256 KB on a Cortex-M-class microcontroller, a search that allocates buckets, width, and bitwidth separately for each track will give higher macro F1 at matched Flash and matched measured latency than a well-tuned "grid-search n-gram ranges, hash to fit, quantize to 8 bits" pipeline. The search costs extraction time as well as table memory. We expect the gap to be largest on tasks with many classes, such as 21-country Arabic dialect identification, and smallest on tasks with few classes, such as three-way sentiment. On a few-class task a hashed linear model is already tiny, so there is little to reallocate. We state this prediction up front because it is also where the proposal could fail.
Where This Sits
The accuracy case for hybrid n-grams motivates the work. Word-plus-character pipelines win on Bangla (SentNoB), on Nepali offensive-language detection across mixed scripts (Niraula et al.), and on Dutch-versus-Flemish discrimination, where they beat syntactic parsers (Kroon et al.). A weighted combination of TF-IDF blocks (word n-grams, character n-grams, boundary-marked character n-grams) beats plain concatenation (Lichouri et al.). That last result suggests the tracks deserve unequal resources. All of these papers set n-gram ranges by hand and report no memory or latency figures. We keep their feature families and add a budget.
Hardware-aware search, meaning methods that pick a network's shape while charging for its measured cost on a target chip, supplies the method. HAT searched Transformer shapes with a learned latency predictor. It found that embedding size strongly affects ARM CPU latency but barely matters on GPUs. HAT nonetheless kept tokenization and embeddings fixed. We search exactly the part HAT held constant.
DUCCIO contributes a loss that penalizes a hardware metric only when it exceeds its budget. This removes repeated tuning of the penalty weight, which the paper reports cuts search time by about 10x. UDC jointly searches layer width, bitwidth, and pruning. Both papers were evaluated only on vision and speech inputs arriving as dense tensors. Neither has a sparse lookup front end or any cost for feature extraction. We reuse DUCCIO's loss and UDC's bitwidth search, and we apply them to a search space made of hash tables.
Word-like character n-gram embedding acts as a constraint. It shows that keeping n-grams by raw frequency wastes memory on meaningless fragments: 35.61% versus 73.64% accuracy on Chinese noun categories. Frequency is therefore a poor selection rule, and our RAM-versus-Flash tiering must be decided by what helps the task, not by frequency alone. Kroon et al. is a second constraint. Their n-gram models latched onto artifacts such as show titles, and a search that rewards accuracy per kilobyte could amplify that tendency. We test for it directly.
Research Program
The model is intentionally small. Each active track hashes its n-grams into its own table. It averages the retrieved vectors, and the per-track averages are concatenated and fed to one linear layer or a one-hidden-layer network. Everything in the model is a lookup, a sum, or a small matrix multiply. That is what makes an accurate cost model feasible.
The weight-sharing supernet, a single over-sized network whose sub-networks are the candidates, is built around one idea: nested hashing. Each track hashes into $2^K$ buckets, and a smaller table of size $2^k$ uses bucket $h \bmod 2^k$. A table of any size is therefore a folding of the largest one and can be trained jointly with it by sampling $k$ during training. Embedding width uses nested channel masks. Bitwidth follows UDC's differentiable scheme over 2, 4, and 8 bits. Each track is switched on or off by a Gumbel-softmax gate, a trick for making a discrete on/off choice trainable by gradient descent. A per-track "hot set" of entries is marked for RAM placement.
We train with
$$\mathcal{L} = \mathcal{L}_{task} + \sum_{j} \lambda_j \max(0, R_j - T_j),$$
where $R_j$ is the predicted Flash, RAM, or latency of the sampled configuration, $T_j$ is its budget, and $\lambda_j$ is a fixed penalty weight, following DUCCIO.
The cost model is new work, because no existing lookup table covers text front ends. We will measure on the device the per-character cost of extracting and hashing each track, lookup latency from Flash versus RAM at each bitwidth, and the cost of the dense layer. From these we build a lookup-table predictor in the style of MoGA, fed with the message-length distribution of each dataset. We validate it against about 100 fully deployed configurations. The analysis output is the chosen allocation itself: which tracks survive at each budget, whether that differs between the microcontroller and a Raspberry Pi-4 (HAT's ARM platform), and whether boundary-marked character n-grams outlast unmarked ones as budgets shrink.
Baselines
The first reference point applies no memory constraint. It is the published uncompressed hybrid n-gram classifier, reported as a ceiling rather than a competitor. The file gives 64.61 macro F1 for the TF-IDF SVM on SentNoB (SentNoB). It gives 0.73 offensive-class F1 for Random Forest on Nepali (Niraula et al.). It gives 0.6201 macro F1 for Naive Bayes and 0.6105 for the hybrid SVM on the Dutch–Flemish DFS task (Kroon et al.). It gives 21.49% F1 on NADI 2021 country-level dialect identification from Lichouri et al.'s ensemble, against a participant average of 24.23% (Lichouri et al.). We re-run these on our splits to get their memory footprints. Our target is to come within 2 F1 points of each ceiling at 128 KB.
The strongest competitor is a strong naive pipeline. It grid-searches word ranges {1, 1–2, 1–3} and character ranges {2–4, 2–5, 1–6, with and without boundaries}. It hashes all tracks into one shared table sized to the Flash budget, trains the same linear or one-hidden-layer head, and applies uniform 8-bit post-training quantization. It gets the same number of trained configurations as our supernet's training cost, measured in GPU-hours, and the same validation protocol. This is the most dangerous comparison because the grid over n-gram ranges is small enough to search exhaustively. Beating it means higher macro F1 at matched Flash and within 10% measured latency, at two or more budgets, on at least three of the four datasets.
The third baseline is the naive pipeline plus UDC-style joint width and bitwidth search, with the front end shared rather than split by track. It isolates what per-track allocation adds beyond known compression search.
Three ablations isolate the key ingredient. The first removes extraction cost from the latency model. The second replaces learned hot-set placement with placement by frequency. The third fixes an equal bucket share across tracks.
Why not just…?
Why not just hash everything into one small table and train a linear model? For three-class sentiment, this may simply win. A linear model's size is buckets times classes, and with three classes even 16k buckets at 4 bits is small, so there is little memory to reallocate. We treat this as a real threat and have built it into our prediction. The shared-table naive baseline is run at every budget. If it matches the search on SentNoB but loses on NADI, the result supports the claim that per-track allocation matters when many classes multiply table cost. If it matches everywhere, the proposal's main claim is false and we will report it that way.
Why not just grid-search n-gram ranges and quantize afterwards? The grid over ranges is cheap, so searching ranges alone is not worth a paper. The grid does not search bucket counts per track, width, bitwidth, or memory placement, and the combined space is far too large to enumerate. UDC showed that joint search over width and bitwidth beats sequential compression by up to 3.35x in size at equal accuracy on vision tasks. Whether that carries over to lookup tables is exactly what the second and third baselines measure.
Why not just compress a small multilingual Transformer? The accuracy evidence points the other way on this data. Multilingual BERT trails n-gram models on Bangla by nearly 12 F1 points (SentNoB) and underperforms on Nepali (Niraula et al.). Its subword vocabulary alone is far larger than our budgets. We therefore report it only as an unconstrained accuracy reference and do not run it on the device.
Proposed Experiments
We run on four datasets: SentNoB, the Nepali offensive-language set, DFS, and NADI 2021. There are two hardware targets. The main one is a Cortex-M-class microcontroller with on-chip Flash. The second is a Raspberry Pi-4, to test whether the chosen allocation changes with the chip, as HAT's findings would predict. The budgets are 32, 64, 128, and 256 KB Flash, under a fixed RAM cap and a per-message latency target.
For each dataset and chip we report macro F1 against measured Flash and latency curves for our method and all baselines, averaged over three seeds. We also report the cost model's error on the deployed configurations. We will not trust search conclusions if the latency error exceeds 15%.
Three checks decide the outcome. The first is whether our method beats the grid-plus-hashing pipeline at matched cost, and whether the size of that margin grows with the number of classes. The second is whether the chosen allocations differ between the microcontroller and the Raspberry Pi, and whether transplanting one chip's allocation to the other loses accuracy. The third is whether gains survive on DFS after stripping the non-linguistic artifacts Kroon et al. identified, such as bracketed tags and show names. A search that wins only by memorizing artifacts would fail this last check.
References
- SentNoB: A Dataset for Analysing Sentiment on Noisy Bangla Texts
- Offensive Language Detection in Nepali Social Media
- When Simple n-gram Models Outperform Syntactic Approaches: Discriminating between Dutch and Flemish
- Arabic Dialect Identification based on a Weighted Concatenation of TF-IDF Features
- HAT: Hardware-Aware Transformers for Efficient Natural Language Processing
- Enhancing Neural Architecture Search With Multiple Hardware Constraints for Deep Learning Model Deployment on Tiny IoT Devices
- UDC: Unified DNAS for Compressible TinyML Models for Neural Processing Units
- Word-like character n-gram embedding
- MoGA: Searching Beyond Mobilenetv3