Computation and Language
Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth
Michelle Yuan, Weiyi Sun, Amir H. Rezaeian et al. (+5 more)
Transformers have become the foundational architecture for a broad spectrum of sequence modeling applications, underpinning state-of-the-art systems in natural
language processing,
vision, and beyond. However, their theoretical limitations in discrete
reasoning tasks, such as arithmetic, logical inference, and algorithmic composition, remain a critical open problem. In this survey, we synthesize recent studies from three theoretical perspectives:
circuit complexity, approximation theory, and communication complexity, to clarify the structural and computational barriers that
transformers face when performing symbolic computations. By connecting these established theoretical frameworks, we provide an accessible and unified account of why current
transformer architectures struggle to implement exact discrete
algorithms, even as they excel at pattern matching and interpolation. We review key definitions, seminal results, and illustrative examples, highlighting challenges such as depth constraints, difficulty approximating discontinuities, and bottlenecks in inter-
token communication. Finally, we discuss implications for model design and suggest promising directions for overcoming these foundational limitations.
Read the full abstract ▾
All authors Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba
Computation and Language
The Script Tax: Measuring Tokenization-Driven Efficiency and Latency Disparities in Multilingual Language Models
Aradhya Dixit and Shreem Dixit
Pretrained
multilingual language models are often assumed to be script-agnostic, yet their tokenizers can impose systematic costs on certain writing systems. We quantify this script tax by comparing two orthographic variants with identical linguistic content. Across mBERT and XLM-R, the higher-fragmentation orthography shows a ~3.4x increase in fertility (6.73-6.85 vs. 2.10-2.35
tokens/word), leading to a 16.5x inference slowdown (0.23 vs. 3.8 sentences/second) on identical hardware. Using bits per character (BPC) to avoid the "NLL paradox" from subword fragmentation, we find a substantial increase in information cost: +19.7% for mBERT (8.06->9.65) and +47.1% for XLM-R (12.19->17.94). A round-trip conversion check (CER_rt=0.31) suggests these gaps reflect orthography-conditioned processing rather than mapping noise. Our results highlight tokenization as a key source of inequity in
multilingual NLP and motivate script-aware tokenization and pretraining.
Read the full abstract ▾
Computation and Language
Author-in-the-Loop Response Generation and Evaluation: Integrating Author Expertise and Intent in Responses to Peer Review
Qian Ruan and Iryna Gurevych
Author response (rebuttal) writing is a critical stage of scientific peer review that demands substantial author effort. In practice, authors possess domain expertise, author-only information, and response strategies - concrete forms of author expertise and intent - and seek NLP assistance that integrates these signals into author response generation (ARG). Yet this author-in-the-loop paradigm lacks formal NLP formulation and systematic study: no
dataset provides fine-grained author signals, existing ARG work lacks author inputs and controls, and no evaluation measures response reflection of author signals and effectiveness in addressing reviewer concerns. To fill these gaps, we introduce (i) Re3Align, the first large-scale
dataset of aligned review-response-revision triplets, where revisions proxy author signals; (ii) REspGen, an author-in-the-loop ARG framework supporting flexible author input, multi-attribute control, and evaluation-guided refinement; and (iii) REspEval, a comprehensive evaluation suite with 20+ metrics spanning input utilization, controllability, response quality, and discourse. Experiments with SOTA LLMs demonstrate the benefits of author input and evaluation-guided refinement, the impact of input specificity on response quality, and controllability-quality trade-offs. We release our
dataset, generation and evaluation tools.
Read the full abstract ▾
Computation and Language
Synthesizing the Virtual Advocate: A Multi-Persona Speech Generation Framework for Diverse Linguistic Jurisdictions in Indic Languages
Aniket Deroy
Legal advocacy requires a unique combination of authoritative tone, rhythmic pausing for emphasis, and emotional intelligence. This study investigates the performance of the Gemini 2.5 Flash TTS and Gemini 2.5 Pro TTS models in generating synthetic courtroom
speeches across five Indic
languages: Tamil, Telugu, Bengali, Hindi, and Gujarati. We propose a prompting framework that utilizes Gemini 2.5s native support for 5
languages and its context-aware pacing to produce distinct advocate personas. The
evolution of Large
Language Models (LLMs) has shifted the focus of TexttoSpeech (TTS) technology from basic intelligibility to context-aware, expressive synthesis. In the legal domain, synthetic
speech must convey authority and a specific professional persona a task that becomes significantly more complex in the linguistically diverse landscape of India. The models exhibit a "monotone authority," excelling at procedural information delivery but struggling with the dynamic vocal modulation and emotive gravitas required for persuasive advocacy. Performance dips in Bengali and Gujarati further highlight phonological frontiers for future refinement. This research underscores the readiness of
multilingual TTS for procedural legal tasks while identifying the remaining challenges in replicating the persuasive artistry of human legal discourse. The code is available at-https://github.com/naturenurtureelite/Synthesizing-the-Virtual-Advocate/tree/main
Read the full abstract ▾
Computation and Language
A Language-Guided Bayesian Optimization for Efficient LoRA Hyperparameter Search
Baek Seong-Eun, Lee Jung-Mok, Kim Sung-Bin et al. (+1 more)
Fine-tuning Large
Language Models (LLMs) with Low-Rank Adaptation (LoRA) offers a resource-efficient way to personalize or specialize. However, LoRA is highly sensitive to hyperparameter choices, and exhaustive hyperparameter search is computationally expensive. To address this, we propose a
Bayesian Optimization (BO) framework that leverages the domain knowledge of pre-trained LLMs to efficiently search for LoRA hyperparameters. Our approach repurposes a pre-trained LLM as a discrete-to-continuous mapping module to link hyperparameters and their domain knowledge to a continuous vector space, where BO is conducted. We design and control the mapping via
language prompting, providing a domain-aware textual
prompt that describes the relationships among hyperparameters and their respective roles. This allows us to explicitly inject domain knowledge about LoRA into the LLM in natural
language. We also introduce an additional learnable
token to capture residual information that is difficult to describe linguistically in the
prompt. This aids BO to sample more high-performing hyperparameters. In addition, by leveraging the strong correlation observed between the performance obtained from full and subset training
datasets in LoRA training regimes, we introduce proxy training and evaluation using a data subset. This significantly improves the efficiency of our method. We demonstrate that our hyperparameter, discovered with only about 30 iterations, achieves more than 20% performance improvement over standard hyperparameters found from about 45,000 combinations. Project page: https://baekseongeun.github.io/lora-bo/
Read the full abstract ▾
All authors Baek Seong-Eun, Lee Jung-Mok, Kim Sung-Bin, Tae-Hyun Oh
Computation and Language
PRIME: Policy-Reinforced Iterative Multi-agent Execution for Algorithmic Reasoning in Large Language Models
Jiawei Xu, Zhenyu Yu, Ziqian Bi et al. (+3 more)
Large
language models have demonstrated remarkable capabilities across diverse
reasoning tasks, yet their performance on algorithmic
reasoning remains limited. To handle this limitation, we propose
PRIME (Policy-Reinforced Iterative Multi-
agent Execution), a framework comprising three specialized
agents, an executor for step-by-step
reasoning, a verifier for constraint checking, and a coordinator for backtracking control, optimized through group relative policy optimization. For comprehensive evaluation, we introduce
PRIME-Bench, the largest algorithmic
reasoning benchmark to date, comprising 86 tasks across 12 categories with 51,600 instances. Tasks span sorting
algorithms, graph and tree structures, automata and state machines, symbolic
reasoning, and constraint-based puzzles, with execution traces reaching over one million steps. Compared to baseline approach,
PRIME improves average accuracy from 26.8% to 93.8%, a 250% relative gain. The largest improvements occur on tasks requiring sustained state tracking, with Turing machine simulation improving from 9% to 92% and long division from 16% to 94%. Ablation studies identify iterative verification as the primary contributor, preventing the error propagation that causes baseline approaches to fail catastrophically. Analysis across model scales (8B-120B parameters) reveals that smaller models benefit disproportionately, achieving accuracy comparable to models 8x larger.
Read the full abstract ▾
All authors Jiawei Xu, Zhenyu Yu, Ziqian Bi, Minh Duc Pham, Xiaoyi Qu, Danyang Zhang
Computation and Language
Disentangling Direction and Magnitude in Transformer Representations: A Double Dissociation Through L2-Matched Perturbation Analysis
Mangadoddi Srikar Vardhan and Lekkala Sai Teja
Transformer hidden states encode information as high-dimensional vectors, yet whether direction (orientation in representational space) and magnitude (vector norm) serve distinct functional roles remains unclear. Studying Pythia-family models, we discover a striking cross-over dissociation: angular perturbations cause up to 42.9 more damage to
language modeling loss, while magnitude perturbations cause disproportionately more damage to syntactic processing (20.4% vs.1.6% accuracy drop on subject-verb agreement).This finding is enabled by L2-matched perturbation analysis, a methodology ensuring that an gular and magnitude perturbations achieve identical Euclidean displacements. Causal intervention reveals that angular damage flows substantially through the
attention pathways (28.4% loss recovery via
attention repair), while magnitude damage flows partly through the LayerNorm pathways(29.9% recovery via LayerNorm repair). These patterns replicate across scales within the Pythia architecture family. These findings provide evidence that direction and magnitude support partially distinct computational roles in LayerNorm based architectures. The direction preferentially affects attentional routing, while magnitude modulates processing intensity for fine-grained syntactic judgments. We find different patterns in RMSNorm-based architectures, suggesting that the dissociation depends on architectural choices. Our results refine the linear representation hypothesis and have implications for model editing and interpretability research
Read the full abstract ▾
Computation and Language
Enhancing SDG-Text Classification with Combinatorial Fusion Analysis and Generative AI
Jingyan Xu, Marcelo L. LaFleur, Christina Schweikert et al. (+1 more)
(Natural
Language Processing) NLP techniques such as text classification and topic discovery are very useful in many application areas including information
retrieval, knowledge discovery, policy formulation, and decision-making. However, it remains a challenging problem in cases where the categories are unavailable, difficult to differentiate, or are interrelated. Social analysis with human context is an area that can benefit from text classification, as it relies substantially on text data. The focus of this paper is to enhance the classification of text according to the UN's Sustainable Development Goals (SDGs) by collecting and combining intelligence from multiple models. Combinatorial Fusion Analysis (CFA), a system fusion paradigm using a rank-score characteristic (RSC) function and cognitive diversity (CD), has been used to enhance classifier methods by combining a set of relatively good and mutually diverse classification models. We use a generative AI model to generate synthetic data for model training and then apply CFA to this classification task. The CFA technique achieves 96.73% performance, outperforming the best individual model. We compare the outcomes with those obtained from human domain experts. It is demonstrated that combining intelligence from multiple ML/AI models using CFA and getting input from human experts can, not only complement, but also enhance each other.
Read the full abstract ▾
All authors Jingyan Xu, Marcelo L. LaFleur, Christina Schweikert, D. Frank Hsu
Computation and Language · Cross-listed from cs.MM
Zihang Wang, Siyue Zhang, Yilun Zhao et al. (+4 more)
Embedding models are a fundamental component of modern AI systems such as semantic search and
retrieval-augmented generation. Recent advances in large foundation models have substantially accelerated the development of
embedding models, including those based on Large
Language Models (LLMs),
Vision Language Models (VLMs), and
Multimodal LLMs. More recently, Large
Diffusion Language Models (dLLMs) and
Multimodal dLLMs have emerged as competitive alternatives to autoregressive models, offering advantages such as bidirectional
attention and parallel generation. This progress naturally raises a critical yet unexplored question: can
Multimodal dLLMs serve as effective
multimodal embedding models? To answer this, we present the first systematic study of converting
Multimodal dLLMs into
embedding models. We evaluate state-of-the-art
Multimodal dLLMs and Autoregressive VLMs across three categories of
embedding tasks: classification, visual question answering, and information
retrieval. Our results show that
Multimodal dLLM
embeddings generally underperform their autoregressive VLM counterparts. The stronger
diffusion-based model, LaViDa, lags by only 3.5 points on classification, 2.5 points on VQA, and 4.4 points on
retrieval tasks, whereas the other
diffusion-based model, MMaDA, exhibits substantially larger performance gaps, exceeding 20 points across all tasks. Further analysis reveals insufficient image-text
alignment in
diffusion-based models, accounting for the observed limitations in their
embedding performance.
Read the full abstract ▾
All authors Zihang Wang, Siyue Zhang, Yilun Zhao, Jingyi Yang, Tingyu Song, Anh Tuan Luu, Chen Zhao
Computation and Language · Cross-listed from cs.IR
AI-assisted Protocol Information Extraction For Improved Accuracy and Efficiency in Clinical Trial Workflows
Ramtin Babaeipour, François Charest and Madison Wright
Increasing clinical trial protocol complexity, amendments, and challenges around knowledge management create significant burden for trial teams. Structuring protocol content into standard formats has the potential to improve efficiency, support documentation quality, and strengthen compliance. We evaluate an Artificial Intelligence (AI) system using generative LLMs with
Retrieval-Augmented Generation (RAG) for automated clinical trial protocol information extraction. We compare the extraction accuracy of our clinical-trial-specific RAG process against that of publicly available (standalone) LLMs. We also assess the operational impact of AI-assistance on simulated extraction Clinical Research Coordinator (CRC) workflows. Our RAG process shows higher extraction accuracy (89.0%) than standalone LLMs with fine-tuned
prompts (62.6%) against expert-supported reference annotations. In simulated extraction workflows, AI-assisted tasks are completed 40% faster, are rated as less cognitively demanding and are strongly preferred by users. While expert oversight remains essential, this suggests that AI-assisted extraction can enable protocol intelligence at scale, motivating the integration of similar methodologies into real-world clinical workflows to further validate its impact on feasibility, study start-up, and post-activation monitoring.
Read the full abstract ▾
Computation and Language · Cross-listed from cs.LG
Extending Beacon to Hindi: Cultural Adaptation Drives Cross-Lingual Sycophancy
Sarthak Sattigeri
Sycophancy, the tendency of
language models to prioritize agreement with user preferences over principled
reasoning, has been identified as a persistent
alignment failure in English-
language evaluations. However, it remains unclear whether such diagnostics generalize across
languages and cultural contexts. We extend the Beacon single-turn forced-choice sycophancy diagnostic to Hindi through a controlled three-condition design: English original, Hindi literal translation, and Hindi culturally adapted
prompts. We evaluate four open-weight instruction-tuned models on 50
prompts per condition, enabling separation of
language encoding effects from cultural adaptation effects. Across all models, sycophancy rates are consistently higher for culturally adapted Hindi
prompts than for English, with absolute differences ranging from 12.0 to 16.0 percentage points. A decomposition on Qwen 2.5-Coder-7B shows that cultural adaptation (delta = 14.0%, 95% CI: [4.0%, 26.0%]) accounts for the majority of this gap, while
language encoding contributes minimally (delta = 2.0%, 95% CI: [0.0%, 6.0%]). Category-level analysis reveals that advice
prompts exhibit the largest cross-lingual differences (20-25 percentage points), achieving statistical significance in two of four models. These findings indicate that
alignment behaviors measured in English may not transfer uniformly across
languages and that culturally grounded
prompt framing plays a substantial role. We release all
datasets and evaluation code to support replication and extension.
Read the full abstract ▾
Computation and Language
In Vino Veritas and Vulnerabilities: Examining LLM Safety via Drunk Language Inducement
Anudeex Shetty, Aditya Joshi and Salil S. Kanhere
Humans are susceptible to undesirable behaviours and
privacy leaks under the influence of alcohol. This paper investigates drunk
language, i.e., text written under the influence of alcohol, as a driver for safety failures in large
language models (LLMs). We investigate three mechanisms for inducing drunk
language in LLMs: persona-based prompting, causal fine-tuning, and reinforcement-based post-training. When evaluated on 5 LLMs, we observe a higher susceptibility to jailbreaking on JailbreakBench (even in the presence of defences) and
privacy leaks on ConfAIde, where both
benchmarks are in English, as compared to the base LLMs as well as previously reported approaches. Via a robust combination of manual evaluation and LLM-based evaluators and analysis of error categories, our findings highlight a correspondence between human-intoxicated behaviour, and anthropomorphism in LLMs induced with drunk
language. The simplicity and efficiency of our drunk
language inducement approaches position them as potential counters for LLM safety tuning, highlighting significant risks to LLM safety.
Read the full abstract ▾
Computation and Language · Cross-listed from cs.DL
LLM-Generated or Human-Written? Comparing Review and Non-Review Papers on ArXiv
Yanai Elazar and Maria Antoniak
ArXiv recently prohibited the upload of unpublished review papers to its servers in the Computer Science domain, citing a high prevalence of LLM-generated content in these categories. However, this decision was not accompanied by quantitative evidence. In this work, we investigate this claim by measuring the proportion of LLM-generated content in review vs. non-review research papers in recent years. Using two high-quality detection methods, we find a substantial increase in LLM-generated content across both review and non-review papers, with a higher prevalence in review papers. However, when considering the number of LLM-generated papers published in each category, the estimates of non-review LLM-generated papers are almost six times higher. Furthermore, we find that this policy will affect papers in certain domains far more than others, with the CS subdiscipline Computers & Society potentially facing cuts of 50%. Our analysis provides an evidence-based framework for evaluating such policy decisions, and we release our code to facilitate future investigations at: https://github.com/yanaiela/llm-review-arxiv.
Read the full abstract ▾
Computation and Language
PhysicsSolutionAgent: Towards Multimodal Explanations for Numerical Physics Problem Solving
Aditya Thole, Anmol Agrawal, Arnav Ramamoorthy et al. (+1 more)
Explaining numerical physics problems often requires more than text-based solutions; clear visual
reasoning can substantially improve conceptual understanding. While large
language models (LLMs) demonstrate strong performance on many physics questions in textual form, their ability to generate long, high-quality visual explanations remains insufficiently explored. In this work, we introduce PhysicsSolutionAgent (PSA), an autonomous
agent that generates physics-problem explanation
videos of up to six minutes using Manim animations. To evaluate the generated
videos, we design an assessment pipeline that performs automated checks across 15 quantitative parameters and incorporates feedback from a
vision-
language model (VLM) to iteratively improve
video quality. We evaluate PSA on 32
videos spanning numerical and theoretical physics problems. Our results reveal systematic differences in
video quality depending on problem difficulty and whether the task is numerical or theoretical. Using GPT-5-mini, PSA achieves a 100%
video-completion rate with an average automated score of 3.8/5. However, qualitative analysis and human inspection uncover both minor and major issues, including visual layout inconsistencies and errors in how visual content is interpreted during feedback. These findings expose key limitations in reliable Manim code generation and highlight broader challenges in
multimodal reasoning and evaluation for visual explanations of numerical physics problems. Our work underscores the need for improved visual understanding, verification, and evaluation frameworks in future
multimodal educational systems
Read the full abstract ▾
All authors Aditya Thole, Anmol Agrawal, Arnav Ramamoorthy, Dhruv Kumar
Computation and Language
MOSLD-Bench: Multilingual Open-Set Learning and Discovery Benchmark for Text Categorization
Adriana-Valentina Costache, Daria-Nicoleta Dragomir, Silviu-Florin Gheorghe et al. (+3 more)
Open-set learning and discovery (OSLD) is a challenging machine learning task in which samples from new (unknown) classes can appear at test time. It can be seen as a generalization of zero-shot learning, where the new classes are not known a priori, hence involving the active discovery of new classes. While zero-shot learning has been extensively studied in text classification, especially with the emergence of pre-trained
language models, open-set learning and discovery is a comparatively new setup for the text domain. To this end, we introduce the first
multilingual open-set learning and discovery (MOSLD)
benchmark for text categorization by topic, comprising 960K data samples across 12
languages. To construct the
benchmark, we (i) rearrange existing
datasets and (ii) collect new data samples from the news domain. Moreover, we propose a novel framework for the OSLD task, which integrates multiple stages to continuously discover and learn new classes. We evaluate several
language models, including our own, to obtain results that can be used as reference for future work. We release our
benchmark at https://github.com/Adriana19Valentina/MOSLD-Bench.
Read the full abstract ▾
All authors Adriana-Valentina Costache, Daria-Nicoleta Dragomir, Silviu-Florin Gheorghe, Eduard Poesina, Paul Irofti, Radu Tudor Ionescu
Computation and Language
Who Endorsed It? Measuring Authority Bias Across Expertise Levels in Language Models
Priyanka Mary Mammen, Emil Joswin and Shankar Venkitachalam
Prior research demonstrates that performance of
language models on
reasoning tasks can be influenced by suggestions, hints and endorsements. However, the influence of endorsement source credibility remains underexplored. We investigate whether
language models exhibit systematic bias based on the perceived expertise of the provider of the endorsement. Across 4
datasets spanning mathematical, legal, and medical
reasoning, we evaluate 11 models using personas representing four expertise levels per domain. Our results reveal that models are increasingly susceptible to incorrect/misleading endorsements as source expertise increases, with higher-authority sources inducing not only accuracy degradation but also increased confidence in wrong answers. We also show that this authority bias is mechanistically encoded within the model and a model can be steered away from the bias, thereby improving its performance even when an expert gives a misleading endorsement.
Read the full abstract ▾
Computation and Language
Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks
Shlok Shelat, Jay Raval, Souvik Roy et al. (+1 more)
Large
language models (LLMs) have demonstrated strong performance on formal
language tasks, yet whether this reflects genuine symbolic
reasoning or pattern matching on familiar constructions remains unclear. We introduce a
benchmark for deterministic finite automata (DFA) construction from regular
languages, comprising factual knowledge questions, seen construction problems from public sources, and two types of unseen problems: hand-crafted instances with multiple interacting constraints and systematically generated problems via Arden's
theorem. Models achieve perfect accuracy on factual questions and 84-90% on seen tasks. However, accuracy drops sharply on unseen problems (by 30-64%), with failures stemming from systematic misinterpretation of
language constraints, incorrect handling of Kleene-
star semantics, and a failure to preserve global consistency. We evaluate a three-stage hint protocol that enables correction of shallow errors but does not reliably resolve globally inconsistent or structurally flawed automata. Our analysis across multiple prompting strategies (direct, Chain-of-Thought, Tree-of-Thought) reveals that errors persist regardless of prompting approach, exposing a fundamental gap between LLMs' ability to generate syntactically plausible DFAs and their capacity for semantically correct formal
reasoning.
Read the full abstract ▾
All authors Shlok Shelat, Jay Raval, Souvik Roy, Manas Gaur
Computation and Language
Structured Insight from Unstructured Data: Large Language Models for SDOH-Driven Diabetes Risk Prediction
Sasha Ronaghi, Prerit Choudhary, David H Rehkopf et al. (+1 more)
Social determinants of health (SDOH) play a critical role in Type 2 Diabetes (T2D) management but are often absent from electronic health records and risk prediction models. Most individual-level SDOH data is collected through structured screening tools, which lack the flexibility to capture the complexity of patient experiences and unique needs of a clinic's population. This study explores the use of large
language models (LLMs) to extract structured SDOH information from unstructured patient life stories and evaluate the predictive value of both the extracted features and the narratives themselves for assessing diabetes control. We collected unstructured interviews from 65 T2D patients aged 65 and older, focused on their lived experiences, social context, and diabetes management. These narratives were analyzed using LLMs with
retrieval-augmented generation to produce concise, actionable qualitative summaries for clinical interpretation and structured quantitative SDOH ratings for risk prediction modeling. The structured SDOH ratings were used independently and in combination with traditional laboratory biomarkers as inputs to linear and tree-based machine learning models (Ridge, Lasso, Random Forest, and XGBoost) to demonstrate how unstructured narrative data can be applied in conventional risk prediction workflows. Finally, we evaluated several LLMs on their ability to predict a patient's level of diabetes control (low, medium, high) directly from interview text with A1C values redacted. LLMs achieved 60% accuracy in predicting diabetes control levels from interview text. This work demonstrates how LLMs can translate unstructured SDOH-related data into structured insights, offering a scalable approach to augment clinical risk models and decision-making.
Read the full abstract ▾
All authors Sasha Ronaghi, Prerit Choudhary, David H Rehkopf, Bryant Lin
Computation and Language
Confidence over Time: Confidence Calibration with Temporal Logic for Large Language Model Reasoning
Zhenjiang Mao, Anirudhh Venkat, Artem Bisliouk et al. (+4 more)
Large
Language Models (LLMs) increasingly rely on long-form, multi-step
reasoning to solve complex tasks such as mathematical problem solving and scientific question answering. Despite strong performance, existing confidence estimation methods typically reduce an entire
reasoning process to a single scalar score, ignoring how confidence evolves throughout the generation. As a result, these methods are often sensitive to superficial factors such as response length or verbosity, and struggle to distinguish correct
reasoning from confidently stated errors. We propose to characterize the stepwise confidence signal using Signal Temporal Logic (STL). Using a discriminative STL mining procedure, we discover temporal formulas that distinguish confidence signals of correct and incorrect responses. Our analysis found that the STL patterns generalize across tasks, and numeric parameters exhibit sensitivity to individual questions. Based on these insights, we develop a confidence estimation approach that informs STL blocks with parameter hypernetworks. Experiments on multiple
reasoning tasks show our confidence scores are more calibrated than the baselines.
Read the full abstract ▾
All authors Zhenjiang Mao, Anirudhh Venkat, Artem Bisliouk, Akshat Kothiyal, Sindhura Kumbakonam Subramanian, Saithej Singhu, Ivan Ruchkin
Computation and Language · Cross-listed from cs.SE
From Completion to Editing: Unlocking Context-Aware Code Infilling via Search-and-Replace Instruction Tuning
Jiajun Zhang, Zeyu Cui, Jiaxi Yang et al. (+9 more)
The dominant Fill-in-the-Middle (FIM) paradigm for code completion is constrained by its rigid inability to correct contextual errors and reliance on unaligned, insecure Base models. While Chat LLMs offer safety and Agentic workflows provide flexibility, they suffer from performance degradation and prohibitive latency, respectively. To resolve this dilemma, we propose Search-and-Replace Infilling (SRI), a framework that internalizes the agentic verification-and-editing mechanism into a unified, single-pass inference process. By structurally grounding edits via an explicit search phase, SRI harmonizes completion tasks with the instruction-following priors of Chat LLMs, extending the paradigm from static infilling to dynamic context-aware editing. We synthesize a high-quality
dataset, SRI-200K, and fine-tune the SRI-Coder series. Extensive evaluations demonstrate that with minimal data (20k samples), SRI-Coder enables Chat models to surpass the completion performance of their Base counterparts. Crucially, unlike FIM-style tuning, SRI preserves general coding competencies and maintains inference latency comparable to standard FIM. We empower the entire Qwen3-Coder series with SRI, encouraging the developer community to leverage this framework for advanced auto-completion and assisted development.
Read the full abstract ▾
All authors Jiajun Zhang, Zeyu Cui, Jiaxi Yang, Lei Zhang, Yuheng Jing, Zeyao Ma, Tianyi Bai, Zilei Wang, Qiang Liu, Liang Wang, Binyuan Hui, Junyang Lin
Computation and Language
Recurrent Confidence Chain: Temporal-Aware Uncertainty Quantification in Large Language Models
Zhenjiang Mao and Anirudhh Venkat
As
reasoning modules, such as the chain-of-thought mechanism, are applied to large
language models, they achieve strong performance on various tasks such as answering common-sense questions and solving math problems. The main challenge now is to assess the uncertainty of answers, which can help prevent misleading or serious
hallucinations for users. Although current methods analyze long
reasoning sequences by filtering unrelated
tokens and examining potential connections between nearby
tokens or sentences, the temporal spread of confidence is often overlooked. This oversight can lead to inflated overall confidence, even when earlier steps exhibit very low confidence. To address this issue, we propose a novel method that incorporates inter-step
attention to analyze semantic correlations across steps. For handling long-horizon responses, we introduce a hidden confidence mechanism to retain historical confidence information, which is then combined with stepwise confidence to produce a more accurate overall estimate. We evaluate our method on the GAOKAO math
benchmark and the CLadder causal
reasoning dataset using mainstream open-source large
language models. Our approach is shown to outperform state-of-the-art methods by achieving a superior balance between predictive quality and calibration, demonstrated by strong performance on both Negative Log-Likelihood and Expected Calibration Error.
Read the full abstract ▾
Computation and Language
Sockpuppetting: Jailbreaking LLMs by Combining Prefilling with Optimization
Asen Dotsinski and Panagiotis Eustratiadis
Prefill attacks are an effective and low-cost jailbreaking method, as they directly insert an acceptance sequence (e.g., "Sure, here is...") at the start of an LLM's output and lead the model to continue the response. We make two contributions to this prior work. First, we show that an unsophisticated adversary can improve the well-known prefill attacks by ensembling a small number of prefill variants. Running three easy-to-generate prefills yields a combined attack success rate (ASR) of 22%, 90%, and 99% on Gemma-7B, Llama-3.1-8B, and Qwen3-8B respectively, an up to 38 percentage point improvement over the standard "Sure, here's..." prefill and up to 82 percentage points over our reproduction of GCG (Zou et al., 2023). Second, we introduce "sockpuppetting", a hybrid attack that optimizes an
adversarial suffix placed inside the "assistant" message block of the chat template, rather than within the user
prompt. The rolling variant of this attack, RollingSockpuppetGCG, increases
prompt-agnostic ASR by up to 64 percentage points over our universal GCG baseline on Llama-3.1-8B. An ablation indicates that part of this gain stems from the choice of acceptance sequence rather than suffix placement alone (Appendix F). Both findings highlight the need for defences against output-prefix injection in open-weight models. Code: https://gitlab.com/asendotsinski/sockpuppetting
Read the full abstract ▾
Computation and Language · Cross-listed from cs.LG
On the Relation of State Space Models and Hidden Markov Models
Aydin Ghojogh, M.Hadi Sepanj and Benyamin Ghojogh
State Space Models (SSMs) and Hidden Markov Models (HMMs) are foundational frameworks for modeling sequential data with latent variables and are widely used in signal processing, control theory, and machine learning. Despite their shared temporal structure, they differ fundamentally in the nature of their latent states, probabilistic assumptions, inference procedures, and training paradigms. Recently, deterministic state space models have re-emerged in natural
language processing through architectures such as S4 and Mamba, raising new questions about the relationship between classical probabilistic SSMs, HMMs, and modern neural sequence models. In this paper, we present a unified and systematic comparison of HMMs, linear Gaussian state space models, Kalman filtering, and contemporary NLP state space models. We analyze their formulations through the lens of probabilistic graphical models, examine their inference
algorithms – including forward-backward inference and Kalman filtering – and contrast their learning procedures via Expectation-Maximization and gradient-based optimization. By highlighting both structural similarities and semantic differences, we clarify when these models are equivalent, when they fundamentally diverge, and how modern NLP SSMs relate to classical probabilistic models. Our analysis bridges perspectives from control theory, probabilistic modeling, and modern deep learning.
Read the full abstract ▾
Computation and Language
LLM-as-RNN: A Recurrent Language Model for Memory Updates and Sequence Prediction
Yuxing Lu, J. Ben Tamo, Weichen Zhao et al. (+5 more)
Large
language models are strong sequence predictors, yet standard inference relies on immutable context histories. After making an error at generation step t, the model lacks an updatable
memory mechanism that improves predictions for step t+1. We propose LLM-as-RNN, an inference-only framework that turns a frozen LLM into a recurrent predictor by representing its hidden state as natural-
language memory. This state, implemented as a structured system-
prompt summary, is updated at each timestep via feedback-driven text rewrites, enabling learning without parameter updates. Under a fixed
token budget, LLM-as-RNN corrects errors and retains task-relevant patterns, effectively performing online learning through
language. We evaluate the method on three sequential
benchmarks in healthcare, meteorology, and finance across Llama, Gemma, and GPT model families. LLM-as-RNN significantly outperforms zero-shot, full-history, and MemPrompt baselines, improving predictive accuracy by 6.5% on average, while producing interpretable, human-readable learning traces absent in standard context accumulation.
Read the full abstract ▾
All authors Yuxing Lu, J. Ben Tamo, Weichen Zhao, Nan Sun, Yishan Zhong, Wenqi Shi, Jinzhuo Wang, May D. Wang
Computation and Language
AfroScope: A Framework for Studying the Linguistic Landscape of Africa
Sang Yun Kwon, AbdelRahim Elmadany and Muhammad Abdul-Mageed
Language Identification (LID), the task of determining the
language of a given text, is a fundamental preprocessing step that shapes the reliability of downstream NLP applications. While recent work has expanded African LID, existing systems remain limited in both
language coverage and fine-grained discrimination among closely related
languages and varieties. We introduce AfroScope, a unified framework for African LID that includes AfroScope-Data, a
dataset covering 640
languages, and AfroScope-Models, a suite of strong LID models with broad African
language coverage. To address persistent confusions among closely related
languages, we propose a hierarchical classification approach that leverages AfroScope-Mirror, a specialized
embedding model for targeted disambiguation, improving macro-F1 by 1.57 points on the confusable subset compared to our best base model. We further analyze cross-lingual transfer and domain effects, showing how
language-family structure, script compatibility, and domain coverage shape LID performance. We position African LID as an enabling technology for large-scale measurement of Africa's linguistic landscape in digital text, and release AfroScope-Data and AfroScope-Models online.
Read the full abstract ▾
Computation and Language
RegCheck: A tool for structured comparisons between study registrations and papers
Jamie Cummins, Beth Clarke, Ian Hussey et al. (+1 more)
Across the social and medical sciences, researchers recognize that specifying planned research activities (i.e., 'registration') prior to the commencement of research has benefits for both the transparency and rigour of science. Despite this, evidence suggests that study registrations frequently go unexamined, minimizing their effectiveness. In a way this is no surprise: manually checking registrations against papers is labour- and time-intensive, requiring careful reading across formats and expertise across domains. The advent of AI unlocks new possibilities in facilitating this activity. We present RegCheck, a modular LLM-assisted tool designed to help researchers, reviewers, and editors from across scientific disciplines compare study registrations with their corresponding papers. Importantly, RegCheck keeps human expertise and judgement in the loop by (i) ensuring that users are the ones who determine which features should be compared, and (ii) presenting the most relevant text associated with each feature to the user, facilitating (rather than replacing) human discrepancy judgements. RegCheck also generates shareable reports with unique RegCheck IDs, enabling them to be easily shared and verified by other users. RegCheck is designed to be adaptable across scientific domains, as well as registration and publication formats. In this paper we provide an overview of the motivation, workflow, and design principles of RegCheck, and we discuss its potential as an extensible infrastructure for reproducible science with an example use case.
Read the full abstract ▾
All authors Jamie Cummins, Beth Clarke, Ian Hussey, Malte Elson
Computation and Language
Reducing Tokenization Premiums for Low-Resource Languages
Geoffrey Churchill and Steven Skiena
Relative to English, low-resource
languages suffer from substantial tokenization premiums in modern LMs, meaning that it generally requires several times as many
tokens to encode a sentence in a low-resource
language than to encode the analogous sentence in English. This tokenization premium results in increased API and energy costs and reduced effective context windows for these
languages. In this paper we analyze the tokenizers of ten popular LMs to better understand their designs and per-
language tokenization premiums. We also propose a mechanism to reduce tokenization premiums in pre-trained models, by post-hoc additions to the
token vocabulary that coalesce multi-
token characters into single
tokens. We apply this methodology to 12 low-resource
languages, demonstrating that the original and compressed inputs often have similar last hidden states when run through the Llama 3.2 1B model.
Read the full abstract ▾
Computation and Language
Arab Voices: Mapping Standard and Dialectal Arabic Speech Technology
Peter Sullivan, AbdelRahim Elmadany, Alcides Alcoba Inciarte et al. (+1 more)
Dialectal Arabic (DA)
speech data vary widely in domain coverage, dialect labeling practices, and recording conditions, complicating cross-
dataset comparison and model evaluation. To characterize this landscape, we conduct a computational analysis of linguistic “dialectness” alongside objective proxies of audio quality on the training splits of widely used DA corpora. We find substantial heterogeneity both in acoustic conditions and in the strength and consistency of dialectal signals across
datasets, underscoring the need for standardized characterization beyond coarse labels. To reduce fragmentation and support reproducible evaluation, we introduce Arab Voices, a standardized framework for DA ASR. Arab Voices provides unified access to 31
datasets spanning 14 dialects, with harmonized metadata and evaluation utilities. We further
benchmark a range of recent ASR systems, establishing strong baselines for modern DA ASR.
Read the full abstract ▾
All authors Peter Sullivan, AbdelRahim Elmadany, Alcides Alcoba Inciarte, Muhammad Abdul-Mageed