Research map / Label-efficient and robust learning / Recognition and long-tail

When Symbol Names Should Not Matter: A Logistic Theory of Fresh-Symbol Classification

NeurIPS 2026 · Label-efficient and robust learning › Recognition and long-tail · approach: Learning from unlabeled and positive-unlabeled data · 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.

Analyzes ridge-regularized kernel logistic regression for fixed-label fresh-symbol classification, decomposing the empirical predictor into an ideal template-level classifier plus a collision-graph perturbation, with high-probability margin-transfer guarantees.

Problem

Whether transformers classify unseen-symbol (fresh-symbol) template instances correctly when training and test share latent templates but use disjoint vocabularies; finite-sample accidental token overlaps may perturb the kernel away from the ideal template problem.

Approach

Reduces the empirical kernel logistic classifier under token symmetry to a template-level ideal classifier plus a perturbation controlled by a colored, signed collision graph, using an entropy-dual analysis of logistic loss to get Lipschitz-type stability bounds and margin-transfer certificates.

Key results

• Main theorem: with probability at least 1 - r exp(-n p_min/8) - delta, the empirical KLR score is within the minimum of five collision-graph certificates of the ideal template score.
• Synthetic experiments show vanilla one-layer transformers generalize to unseen symbols only with large samples, while K-Q and V-O multipliers substantially improve generalization; K-Q multiplier dominates for classification.
• Collision-graph certificates are compared against scalar proxy w_max/rho on eight finite template tasks (Figure panel c), with improvements shown in some cases.

Surprising findings

• Two collision schemes with identical token frequencies and edge-token counts can yield very different classification behavior, so scalar vocabulary diversity rho is only a marginal proxy.
• In the alpha-beta-alpha vs alpha-beta-beta example, the signed collision residual cancels in every row and column even though the support matrix has density 1/2.

Limitations

• Theory restricted to one-layer frozen-feature transformer kernel regime; does not capture representation learning in trained deep transformers.
• Experiments limited to synthetic template tasks, not natural language.
• Does not address optimization dynamics, finite-width effects, or implicit bias in end-to-end training.

Experimental setup

Datasets: synthetic template tasks (alpha beta alpha vs alpha beta beta; majority task)

Benchmarks: synthetic template classification tasks majority task

Metrics: test accuracy test error certificate magnitude vs scalar proxy

Baselines: scalar diversity bound B_rho = w_max/rho

Builds on: Boix-Adserà et al. fresh-symbol framework neural tangent / random-feature kernel analysis kernel ridge regression theory

Closest papers by meaning

• Effective Context in Transformers: An Analysis of Fragmentation and Tokenization (NeurIPS 2026 · similarity 0.86)
• Logits are All We Need to Adapt Closed Models (ICML 2025 · similarity 0.84)
• Rethinking Tokenized Graph Transformers for Node Classification (NeurIPS 2025 · similarity 0.84)
• An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.83)
• Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling (ICML 2025 · similarity 0.83)
• A distributional simplicity bias in the learning dynamics of transformers (NeurIPS 2024 · similarity 0.82)