Computation and Language
End-to-End Context Compression at Scale
Ang Li, Sean McLeish, Haozhe Chen et al. (+12 more)
Long-context
language model inference is bottlenecked by
memory, as the KV cache grows with context length. Recent techniques to compress the KV cache fall short: they either degrade model quality substantially or require considerable time and compute to compress a single long
prompt. Furthermore, many methods require the input to fit within the target model's context window, and are generally incompatible with modern production inference engines. Encoder-decoder compressors, which map a long
token sequence to a shorter sequence of latent
embeddings consumed by a decoder, are an appealing alternative in principle. However, existing approaches are not competitive with KV cache compression on the accuracy-efficiency frontier. In this work, we revisit encoder-decoder compression and close this gap. We first perform an architecture search, pre-training many variants from scratch to determine how best to design and train encoder-decoder compressors. Guided by our findings, we continually pre-train a family of 0.6B-encoder, 4B-decoder models on nearly 400B
tokens each, at compression ratios of 1:4, 1:8, and 1:16. We introduce Latent Context
Language Models (LCLMs), a family of compressors that improve the Pareto frontier across general-task performance, compression speed, and peak
memory usage. LCLMs also unlock new efficient downstream applications: they serve as backbones for long-horizon
agents that skim a compressed long context and adaptively expand relevant segments on demand, and they can compact the model's own generated
reasoning into latent
memory during inference, which is nearly lossless on the full MATH test set while being highly efficient, reducing peak KV usage by up to $7.9\times$.
Read the full abstract ▾
All authors Ang Li, Sean McLeish, Haozhe Chen, Nimit Kalra, Zaiqian Chen, Artem Gazizov, Venkata Anoop Suhas Kumar Morisetty, Bhavya Kailkhura, Harshitha Menon, Zhuang Liu, Brian R. Bartoldson, Tom Goldstein, Sanae Lotfi, Micah Goldblum, Pavel Izmailov
Computation and Language
Beyond Accuracy: Community Perspectives on Machine Translation
Yujun Wang, Ehud Reiter, Shimei Pan et al. (+2 more)
Despite remarkable progress in machine translation (MT), non-AI communities have raised growing concerns about MT systems, suggesting a noticeable gap between technical advancement and the needs of real-world users. For instance, while NLP researchers focus on
benchmark performance, end users care about ethical concerns, trust, reliability, costs, and more. We argue that listening to various user communities is essential so that research efforts would be directed towards the problems that the communities care about. To this end, we present a large-scale analysis, for the first time, that investigates what four stakeholder communities (AI developers, professional translators,
language learners, and
language service providers) post about MT technology on social media. To do so, we construct a
dataset of 79,286 posts and comments from Reddit, Facebook, Bluesky, and Mastodon from 2019 to 2025, and analyse where these communities disagree, and how and why. Overall, we find that communities often disagree, and even show strong conflicts due to polarised sentiments on topics such as translation quality, efficiency, and reliability. This is because these communities approach these topics differently: the AI community frames them as technical and computational problems, while non-AI (user) communities care more about quality nuances, time savings, user trust, and broader social issues.
Read the full abstract ▾
All authors Yujun Wang, Ehud Reiter, Shimei Pan, Steffen Eger, Wei Zhao
Computation and Language
Where Does the Answer Come From? Benchmarking View-Level Visual Evidence Identification in Multi-View MLLMs for Autonomous Driving
Yimu Wang, Yee Man Choi, Barry Zhang et al. (+3 more)
Multimodal large
language models (MLLMs) achieve strong results on visual
reasoning benchmarks, but answer accuracy alone does not indicate whether a model relied on the correct visual evidence. This gap is particularly important in multi-view driving scenes used for autonomous driving, where a model can produce a plausible answer while grounding it in the wrong camera view. We introduce a multi-view visual question answering
benchmark for evaluating evidence-source identification: given six synchronized NuScenes views and a question, the model must identify the supporting camera view and answer the question. The
benchmark contains 122 conflict-centric question-answer pairs from 73 scenes, spanning causality, counterfactual
reasoning, and intent prediction. View labels are proposed by an automatic conflict-mining pipeline and manually verified by annotators. We evaluate three settings: camera-view selection, oracle QA given the golden view, and joint prediction in which the model selects a view and answers in one pass. Answers are evaluated in both multiple-choice and free-form formats, using exact match for structured predictions and an LLM judge for free-form responses. By explicitly separating visual-source identification from answer correctness, the
benchmark exposes grounding failures that answer-only evaluation misses.
Read the full abstract ▾
All authors Yimu Wang, Yee Man Choi, Barry Zhang, Mozhgan Nasr Azadani, Sean Sedwards, Krzysztof Czarnecki
Computation and Language
Gradient-Guided Reward Optimization for Inference-time Alignment
Hankun Lin and Ruqi Zhang
Ensuring the reliability of Large
Language Models (LLMs) under distribution drift requires inference-time adaptation. While inference-time
alignment methods such as Best-of-$N$ and rejection sampling are widely used, they frame the task as a sampling-intensive, reward-guided search, leading to two key limitations: their performance is bounded by the base model's generation quality, and their reliance on imperfect reward models makes them vulnerable to reward hacking. To address these challenges, we introduce Gradient-Guided Reward Optimization (GGRO), a lightweight inference-time method that performs targeted, minimal intervention during decoding via gradient guidance. Specifically, GGRO monitors
token-level
entropy to identify high-uncertainty regions indicative of drift or misalignment. Upon detection, it responds by injecting nudging
tokens, generated using gradient signals from an off-the-shelf reward model, to steer the generation trajectory rather than merely re-ranking samples. Experiments show that GGRO consistently improves inference-time
alignment across safety, helpfulness, and
reasoning benchmarks. It also increases coverage of high-quality responses and robustness to reward hacking, with minimal computational overhead. Code is available at https://github.com/lhk2004/GGRO.
Read the full abstract ▾
Computation and Language
Civil Court Simulation with Large Language Models
Yifan Chen, Haitao Li, Kaiyuan Zhang et al. (+3 more)
Court simulation bridges legal education and judicial practice, yet human-based simulations are costly and difficult to scale. Large
language models (LLMs) offer a scalable alternative, but existing court-simulation research mainly focuses on criminal cases. Civil litigation is more common in practice and harder to simulate because its claims, liability, and remedies are more flexible. We present a multi-
agent court simulation framework for Chinese civil cases. The framework organizes role-based interaction through a five-stage civil trial procedure and integrates
memory module and statute
retrieval to support long-process adjudication. Experiments show that the framework produces reliable civil judgments, with clear strengths in liability allocation and multi-item adjudication. Further experiments show that
memory quality substantially affects downstream simulation quality. Through a five-layer factor framework, we analyze how legal grounding, information conditions, judicial capability and role orientation, organizational pressure, and social context affect the framework's reliability and behavior. These results support the effectiveness of the proposed framework for civil court simulation. The
dataset and code are available at: https://github.com/foggpoy/Civil-Court.
Read the full abstract ▾
All authors Yifan Chen, Haitao Li, Kaiyuan Zhang, Yueyue Wu, Qingyao Ai, Yiqun Liu
Computation and Language
AgentServeSim: Serving-System Simulation and Policy Search for LLM Agent Programs
Rakibul Hasan Rajib, Mengxin Zheng and Qian Lou
Large
language model
agents execute programs comprising multiple model turns interleaved with external tool calls. Their job completion time depends on how the serving system retains KV state across tool gaps, routes successor turns, and schedules competing programs. Most existing serving simulators operate on request streams in which arrivals are externally supplied and KV state follows request- or cache-scoped semantics. They therefore cannot jointly represent the cross-turn state and policy-dependent successor releases needed to evaluate counterfactual
agent-serving trajectories. We present AgentServeSim, a simulator whose unit of execution is the
agent program. A Program Control Block maintains cross-turn state, while a Program Orchestrator causally releases successor turns from simulated predecessor completions. A Retention Plane controls KV state across tool gaps, and a Dispatch Plane determines where and when each ready turn executes. We validate AgentServeSim against real vLLM deployments in 20 paired simulator-real
cells spanning two GPU platforms, Llama-3.1-8B and Llama-3.1-70B, coding and function-calling
agents, and five arrival rates. Mean JCT error remains within 5.5% on B200 and 5.2% in the saturated RTX PRO 6000 regime. Finally, we propose LLM-driven automated
agent-serving policy search using AgentServeSim as a CPU-based fitness evaluator. The resulting policies improve mean JCT over hand-written seed policies by 0.5% for KV retention and 2.8% for scheduling.
Read the full abstract ▾
Computation and Language
Automated IEP Generation from Traditional Chinese Parent-Teacher Interviews via Corpus-Grounded Feature Diffusion
Kuanlin Chen and Cheng-En Ou
Writing Individualized Education Programs (IEPs) is a high-labor, knowledge-intensive document burden; English-
language research has demonstrated that generative AI can significantly reduce drafting time, yet automated IEP generation in Traditional Chinese remains virtually unexplored due to domain data scarcity, strict
privacy regulations, and the absence of local evaluation
benchmarks. We propose a low-resource fine-tuning pipeline centered on Corpus-Grounded Feature
Diffusion (CGFD): (1) 25 dual-expert high-score seed transcripts are selected via a tau threshold with flag-aware score caps; (2) a FeatureProfile (sentence length, structure, quantification templates) is extracted from seeds and injected into LLM
prompts alongside Verbalized-Sampling-style diversity control to drive
diffusion; (3) 15 expert gold seeds are used as
diffusion anchors, targeting 585 samples; 567 valid
diffusion samples are obtained, yielding a 582-sample training set used to fine-tune Breeze-7B with QLoRA; (4) schema-constrained inference via Grammar-Constrained Decoding (GCD) enforces a hierarchical SMART Goal Ladder schema at inference time. Ablation results on a 55-sample schema stress set reveal an unexpected finding: GCD is counterproductive under Traditional Chinese
token budgets – the no-GCD path achieves 100% schema pass rate at 34% lower median latency, outperforming GCD on both reliability and speed. On the n=10 formal hold-out, the no-GCD inference path achieves BERTScore F1 = 0.779, exceeding GPT-5.4 (0.726), DeepSeek-V3.2 (0.703), Gemini-3-Flash-Preview (0.703), and Llama-4-Maverick (0.700) zero-shot baselines while maintaining fully local, air-gapped inference. This system addresses a gap in Traditional Chinese special-education NLP and offers a scalable,
privacy-preserving local inference solution under an industrial engineering paradigm.
Read the full abstract ▾
Computation and Language
Clinically Grounded Privacy Evaluation of Medical LMs
Sasha Ronaghi, Sana Tonekaboni, Lena Stempfle et al. (+6 more)
Medical
language models (LMs) can memorize and reproduce protected health information, but
privacy evaluations often focus on recovery of training text rather than disclosure under realistic threat models. We introduce a clinically grounded framework that evaluates leakage along a graded axis of
adversarial access, ranging from publicly inferable demographics to leaked note fragments. At each tier, we measure verbatim memorization of patient-specific text and semantic leakage of sensitive diagnoses. Applying the framework to an LM continually pretrained on 378k clinical notes, we find that routine encounter metadata (i.e., name, date of birth, visit date, provider name, and practice location) elicits high rates of verbatim memorization across a patient's timeline and sensitive-diagnosis recovery (AUROC 0.91 for abortion, 0.82 for HIV). At the same time, exact-match memorization can overstate disclosure: 36% of memorized
tokens reflect templated documentation. Our work highlights the risks of training on longitudinal clinical data and provides a practical, reusable framework for contextual
privacy evaluation of medical LMs.
Read the full abstract ▾
All authors Sasha Ronaghi, Sana Tonekaboni, Lena Stempfle, Vivian Utti, Jordan Li Cahoon, Nathaniel Hendrix, Ayin Vala, Marzyeh Ghassemi, Emily Alsentzer
Computation and Language · Cross-listed from cs.AI
TABVERSE: Benchmarking Cross-Format Table Understanding in LLMs and VLMs
Momina Ahsan, Sarfraz Ahmad, Ming Shan Hee et al. (+2 more)
Large
Language Models (LLMs) and
Vision-
Language Models (VLMs) are increasingly evaluated on table
reasoning tasks, but the role of table representation remains under-explored. In practice, the same table content may appear in different structural formats, such as HTML, Markdown, and LaTeX, or as rendered images. However, existing evaluations often let content, format, layout, and modality vary together, making it difficult to isolate representation effects. We introduce TABVERSE, a controlled
multimodal table
benchmark that aligns the same table content across multiple structural formats and rendered images, with question category and difficulty tags. This design enables systematic evaluation of representation effects while holding table content fixed. We evaluate LLMs and VLMs across three tasks: Question Answering (QA), Structural Understanding Capability (SUC), and Structure Reconstruction (SR). Our results show that representation choice substantially affects table understanding. Models generally perform better with structured text than with rendered images, but the size of this gap depends on the task, model, and format. HTML is often the most robust text format, while row-sensitive structural tasks and syntactically usable LaTeX reconstruction remain challenging. These findings show that table representation is a key factor in reliable table evaluation.
Read the full abstract ▾
All authors Momina Ahsan, Sarfraz Ahmad, Ming Shan Hee, Roy Ka-Wei Lee, Preslav Nakov
Computation and Language
Code Is More Than Text: Uncertainty Estimation for Code Generation
Yuling Shi, Caiqi Zhang, Yuexian Li et al. (+4 more)
Large
language models (LLMs) are increasingly deployed as code generators, where silently wrong programs pose real safety and reliability risks. Reliable uncertainty estimation (UE) is essential for selective prediction, human-in-the-loop review, and downstream agentic decisions. Yet most existing code UE methods are inherited from natural
language (NL) generation and ignore properties that make code distinct. We argue that code differs from NL in three ways: a single wrong
token can break an entire program (
token fragility); algorithmic intent and concrete implementation can disagree independently (intent-code gap); and programs can be executed (executability). We instantiate these properties as three orthogonal uncertainty axes: lexical (Top-K
token entropy), algorithmic (pseudo-code consistency), and functional (behavioral consistency). Across five code LLMs, our three-axis ensemble improves average AUROC from 0.696 for the strongest NL-derived baseline to 0.776 (+8.1 points). Notably, on Qwen3-14B, our single-pass Top-K
token entropy matches the strongest multi-pass baseline while being over 3x cheaper; across models, it remains a competitive low-cost signal. These results suggest that code UE deserves code-specific design rather than direct NL ports.
Read the full abstract ▾
All authors Yuling Shi, Caiqi Zhang, Yuexian Li, Haopeng Wang, Yeheng Chen, Nigel Collier, Xiaodong Gu
Computation and Language
UXBench: Benchmarking User Experience in AI Assistants
Mengze Hong, Xia Zeng, Zeyang Lei et al. (+13 more)
As AI assistants serve millions of users daily, evaluating user experience (UX) beyond general model capability has become increasingly important. We present UXBench, the first user-centric
benchmark grounded in real user feedback signals for evaluating preference
alignment and dialogue generation. The
benchmark consists of three interconnected tasks, UX Judge, UX Eval, and UX Recovery, with 7,400 test instances extracted from over 70K interaction logs of a mainstream Chinese AI assistant. The
dataset closely reflects real user distributions, covering 8 scenarios, 83 domains, and diverse failure patterns that pose severe challenges. Extensive experiments on 26 frontier
language models provide novel insights into how well models perceive user experience and how improvements in model capability contribute to better dialogue engagement. Through analyses of model behavior and performance gaps, we document six important findings, demonstrating that user feedback prediction is a learnable capability and revealing different aspects that influence user experience. UXBench establishes a new evaluation landscape and calls for greater
attention to tailored UX optimization, contributing toward a user-centric scaling law for the development of successful AI assistants. The full project is released at https://github.com/mengze-hong/UXBench.
Read the full abstract ▾
All authors Mengze Hong, Xia Zeng, Zeyang Lei, Sheng Wang, Chen Jason Zhang, Di Jiang, Taiming Fu, Jinfeng Huang, Mengqiao Liu, Qinghe Chang, Haosheng Zou, Qiongyi Zhou, Sijun He, Xiaoshuai Chen, Minlong Peng, Di Liang
Computation and Language
OpenBibleTTS: Large-Scale Speech Resources and TTS Models for Low-Resource Languages
David Guzmán, Luel Hagos Beyene, Jesujoba Oluwadara Alabi et al. (+3 more)
Recent advances in neural text-to-
speech (TTS) and
multilingual speech generation have substantially improved synthetic
speech quality, yet these gains remain unevenly distributed across the world's
languages. Existing models are still dominated by a small set of high-resource
languages, while many studies of low-resource TTS are simulated on artificially downsampled high-resource corpora that do not reflect the orthographic variation and limited phonetic coverage encountered in genuinely underrepresented settings. As such, we introduce OpenBibleTTS, which is a large-scale
benchmark for low-resource
speech synthesis spanning 37 underrepresented
languages. Moreover, a systematic comparison of various TTS architectures and large-scale
speech generation models is conducted across in-domain Biblical text and out-of-domain material. Results show that no single system dominates across
languages and metrics: Gemini-TTS achieves the highest listener ratings on most evaluated
languages, but monolingual EveryVoice models trained on OpenBibleTTS remain strongest for intelligibility and are preferred in several African
languages, while open from-scratch systems degrade sharply on out-of-domain text, revealing a persistent gap between broad
multilingual coverage and reliable synthesis quality in underserved linguistic communities. We complement automatic evaluation with subjective human judgments, and open-source all processed
datasets,
alignments, and trained models to support future low-resource TTS research.
Read the full abstract ▾
All authors David Guzmán, Luel Hagos Beyene, Jesujoba Oluwadara Alabi, Yejin Jeon, Dietrich Klakow, David Ifeoluwa Adelani
Computation and Language
From Genes to Tokens: a GWAS-inspired Approach for Interpretable Stylometric Analysis
Dmitry Pronin and Evgeny Kazartsev
This short paper introduces a stylometric interpretation method inspired by genome-wide association studies (GWAS). Each "gene"
token's association with "phenotype" authorship is tested using logistic regression with multiple-comparison correction. Applied to English, German, and Russian corpora, the method detects statistically significant lexical markers distinctive of individual authors.
Read the full abstract ▾
Computation and Language
Overcoming Decoder Inconsistencies in Whisper for Dravidian and Low-Resource Languages
Chowdam Venkata Kumar, Kumud Tripathi and Pankaj Wasnik
Multilingual ASR models such as Whisper perform well on high-resource
languages but exhibit substantially higher Word Error Rates (WER) for Dravidian
languages compared to Indo-Aryan ones. Through linguistic and
dataset analysis, we show that Dravidian
languages have longer words, higher vocabulary diversity, and lower repetition, resulting in sparse
token distributions and frequent character-level substitution errors. Baseline fine-tuning further reveals decoder imbalance between self-
attention (linguistic context) and cross-
attention (acoustic cues). Although synthetic
token-repetition experiments indicate potential gains, they are impractical. Motivated by these observations, we introduce two decoder-level enhancements: Weighted-
Attention, which adaptively balances
attention sources, and Self-Conditioning, which reinjects intermediate predictions to improve
token consistency. Experiments demonstrate consistent WER reductions for low-resource and agglutinative
languages.
Read the full abstract ▾
Computation and Language · Cross-listed from cs.CY
Interpretable Crisis Behavior Analysis Using Mobility and Social Media Data
Muhammad Hamza Arshad Majeed, Sidahmed Benabderrahmane and Talal Rahwan
Crises alter both how people move and how they communicate. During emergencies such as wildfires and pandemics, changes in mobility patterns and online emotional discourse evolve jointly, yet they are typically studied in isolation. This paper presents a unified and interpretable pipeline that integrates mobility and social media data to identify cross-domain behavioral patterns in crisis settings. The framework is evaluated through two case studies: a short-horizon analysis of the January 2025 Los Angeles wildfires (prototype case) and a longitudinal analysis of UAE COVID-19 behavior from March 2020 to December 2021 (primary case, 671 days). The pipeline aligns heterogeneous daily signals, transforms them into binary behavioral states, applies Formal Concept Analysis (FCA) to extract co-occurrence structure, mines association rules, and validates rule stability through chronological holdout testing. A structured policy-translation layer renders robust rules as operational briefs specifying triggers, lead times, and action playbooks. Results reveal clear cross-domain behavioral structure in both crises. In the wildfire case, traffic stress, fear/anger sentiment, and governance discourse are tightly coupled within a 33-day window, with key rules reaching 100% confidence and lift scores up to 2.5. In the COVID case, repeated mobility adaptation and sentiment
volatility yield 8 stable same-day rules (88% holdout pass rate) and 40 clean predictive rules with 2–7 day lead horizons. The work demonstrates that interpretable
multimodal fusion can produce both scientifically credible and policy-actionable crisis intelligence.
Read the full abstract ▾
Computation and Language
Emergence of Context Characteristics Sensitivity in Large Language Models
Nadya Yuki Wangsajaya, Haeun Yu and Isabelle Augenstein
During instruction fine-tuning (IFT), large
language models (LLMs) learn to follow instructions by using the provided context to answer a query. While prior work has studied how context characteristics correlate with context usage by the LLM, this analysis has been limited to inference time, leaving open how these relationships are acquired in the first place. Here, we measure how models' sensitivity to such characteristics shifts across successive IFT stages: supervised fine-tuning (SFT), direct preference optimization (DPO), and reinforcement learning with verifiable rewards (RLVR). Experiments across four models and three
datasets show that SFT makes models more likely to use contexts that are easy to understand, such as containing high length, context-query similarity, and fluency. Post-SFT dynamics may either reinforce or resolve these preferences depending on the training
dataset. Our findings reveal that context usage is actively reshaped at each IFT stage, and designing a balanced IFT
dataset is important in ensuring robust context utilization of instruction-tuned models.
Read the full abstract ▾
Computation and Language · Cross-listed from cs.AI
From Rigid to Dynamic: Entropy-Guided Adaptive Inference for Long-Context LLMs
Zhanchao Xu, Haoyang Li, Qingfa Xiao et al. (+4 more)
Existing sparse
attention and KV cache compression methods for long-context LLM inference typically apply fixed sparsity patterns or uniform budgets across all
attention heads, overlooking the substantial variation in
attention behavior among heads and contexts. We observe two distinct
entropy patterns among
attention heads: Rigid Heads, whose
entropy stays near zero across input segments, and Dynamic Heads, whose
entropy fluctuates significantly. Crucially, the distribution of these types is context-dependent and cannot be predetermined offline. We therefore propose EntropyInfer, a training-free framework that uses
attention entropy to adaptively allocate compute at the granularity of individual heads and segments during prefilling. For decoding, we introduce a latent KV cache compression scheme that leverages generated output
tokens, rather than prefill
tokens alone, to identify and retain the most critical cache entries. Extensive experiments on Llama, Qwen and openPangu model series show that EntropyInfer consistently outperforms baselines including SnapKV, AdaKV, and CritiPrefill, achieving up to 2.39$\times$ end-to-end speedup beyond 100k
tokens with minimal quality degradation compared to full
attention. The code is released in https://github.com/SHA-4096/EntropyInfer.
Read the full abstract ▾
All authors Zhanchao Xu, Haoyang Li, Qingfa Xiao, Fei Teng, Chen Jason Zhang, Lei Chen, Qing Li
Computation and Language
Self-Harness: Harnesses That Improve Themselves
Hangfan Zhang, Shao Zhang, Kangcong Li et al. (+5 more)
The performance of LLM-based
agents is jointly shaped by their base models and the harnesses that mediate their interaction with the environment. Because different models exhibit distinct behaviors, effective harness design is inherently model-specific. Yet
agent harnesses are still largely engineered by human experts, a paradigm that scales poorly as modern LLMs become increasingly diverse and rapidly evolving. In this paper, we introduce Self-Harness, a new paradigm in which an LLM-based
agent improves its own operating harness, without relying on human engineers or stronger external
agents. We operationalize Self-Harness as an iterative loop with three stages: Weakness Mining, which identifies model-specific failure patterns from execution traces; Harness Proposal, which generates diverse yet minimal harness modifications tied to these failures; and Proposal Validation, which accepts candidate edits only after regression testing. We instantiate Self-Harness across Terminal-Bench-2.0, SWE-bench Verified, and AppWorld using a minimal initial harness and three base models from diverse families: MiniMax M2.5, Qwen3.5-35B-A3B, and GLM-5. Across all nine model–
benchmark combinations, every final harness improves both held-in and held-out pass rates, with overall relative gains of up to 132%. Qualitative analyses further show that the retained mechanisms address
benchmark-specific bottlenecks in artifact handling and runtime control, software-patch verification, and application-state
retrieval. These results suggest a path toward LLM-based
agents that are not merely shaped by their harnesses, but can also participate in reshaping them.
Read the full abstract ▾
All authors Hangfan Zhang, Shao Zhang, Kangcong Li, Chen Zhang, Yang Chen, Yiqun Zhang, Lei Bai, Shuyue Hu
Computation and Language
Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
Kumar Thushalika, Sukumar Kishanthan and Asela Hevapathige
Large
language models (LLMs) have shown impressive performance on diverse
reasoning tasks, yet their capacity for structural
reasoning in graphs remains unclear. We investigate whether LLMs can genuinely understand graph isomorphism -a fundamental problem in graph theory. While LLMs achieve near-perfect accuracy on isomorphism detection, we show this performance is illusory. When identical graphs are presented with permuted node labels, LLMs fail to identify their isomorphism. This finding suggests that LLMs exploit patterns rather than
reasoning about abstract graph structure. Since permutation invariance is a fundamental requirement for valid structural
reasoning, these results indicate that success on graph
reasoning benchmarks should not be interpreted as evidence of genuine topological understanding.
Read the full abstract ▾
Computation and Language
Memory Beyond Recall: A Dual-Process Cognitive Memory System for Self-Evolving LLM Agents
Tianxiang Fei, Mingyang Song, Mao Zheng et al. (+1 more)
Long-term
memory for an LLM
agent is more than retrieving the right passage at the right time. Current
memory systems collapse belief revision, causal coupling, and cross-domain abstraction into a single
retrieval surface tuned for surface recall, and consequently struggle on implicit personalisation that requires
reasoning over how a user has evolved. We propose DCPM, which reorganises
agent memory along a cognitive capability hierarchy ascending from raw inputs and atomic facts, through diachronic belief trajectories and identity, to domain schemas, latent intentions and cross-domain patterns. The hierarchy is driven by two processes inheriting the architectural split of dual-process theory: a synchronous daytime writer (System1) that records belief revisions as doubly linked supersedes chains, and an asynchronous nighttime engine (System2) that induces schemas and intentions and sweeps for cross-domain collisions abstracted into higher-level core schemas. On LongMemEval, PersonaMem and PersonaMem-v2, enabling System2 contributes most where the
benchmark rewards implicit cross-session inference (up to +5.20 on PersonaMem-v2) and least on span recall, matching the architectural prediction.
Read the full abstract ▾
All authors Tianxiang Fei, Mingyang Song, Mao Zheng, Xiang Yu
Computation and Language · Cross-listed from cs.LG
Escaping the KL Agreement Trap in On-Policy Distillation
Haoran Xin, Anhao Zhao, Ying Sun et al. (+3 more)
On-policy
distillation (OPD) provides dense
token-level supervision by asking a teacher to score student-generated rollouts. However, when the student drifts into an unrecoverable prefix, the teacher may locally agree with the degraded state, producing low reverse KL but little corrective training signal. We identify this persistent regime as a low-KL agreement trap. Further analyses show that
tokens during and after such traps produce less useful supervision signals. We propose KAT (KL Agreement Trap Termination), an online OPD termination rule that detects persistent low-KL agreement with a dynamic training-adaptive threshold. By filtering weak supervision from degenerate agreement, KAT improves avg@k accuracy by 2.66% and pass@k by 3.43% across four mathematical
benchmarks, while reducing average rollout length by 59.73%.
Read the full abstract ▾
All authors Haoran Xin, Anhao Zhao, Ying Sun, Jin Li, Xiaoyu Shen, Hui Xiong
Computation and Language
A Finetuned SpeechLLM for Joint Multi-Granular L2 Assessment and Natural-Language Rationales
Aditya Kamlesh Parikh, Cristian Tejedor-Garcia, Catia Cucchiarini et al. (+1 more)
Automated L2
speech assessment can assign proficiency labels, but often lacks interpretability. We propose a rubric-guided SpeechLLM for multi-aspect, multi-granular assessment, trained with a hybrid objective combining supervised fine-tuning and Bounded Direct Preference Optimization. The model jointly predicts ordinal labels at the sentence-level (accuracy, fluency, prosody), word/phoneme-level accuracy, and generates a natural-
language rationale in the same response. On SpeechOcean762, our approach matches or outperforms single-granularity models while remaining competitive with prior approaches. We analyze rationale reliability along two axes: self-consistency with model predictions and
alignment with ground-truth labels, using sentiment consistency (plausibility) and mention-based agreement (faithfulness). Rationales are plausible at the sentence level, but faithfulness degrades at the word/phoneme level: references are sparse and weakly aligned with
token-level labels.
Read the full abstract ▾
All authors Aditya Kamlesh Parikh, Cristian Tejedor-Garcia, Catia Cucchiarini, Helmer Strik
Computation and Language
DECSELFMASK: Leveraging Unlabeled Text via Self-Relevance-Guided Masking for Decoder-Only Classification
Pietro Ferrazzi, Matteo Merler, Giovanni Bonetta et al. (+2 more)
Classification tasks require annotated data, which can often be expensive, time-consuming, or even unfeasible to collect. This is the case of the medical domain, where large
datasets often have few annotated examples. To address this, we propose DecSelfMask (Decoder Self-learning by Masking), an approach to enhance decoder-only performance on classification tasks. We build on common self-learning approaches by leveraging a model to create training examples from unlabeled data, and propose a novel relevance-guided masking strategy. We use relevance attribution methods to determine what portions of unannotated texts are relevant for a task. We then create self-supervised training examples by masking out those portions, training the model to reconstruct them via next-
token-prediction. We hypothesize that those examples convey knowledge about the structure and semantics of unannotated data that can be useful for downstream performance. We test our approach on 136 tasks from a collection of 1.9M clinical notes from an Italian hospital. We quantify DecSelfMask's impact on downstream tasks on 5 models of different scales and families, including a probing analysis. Experiments show consistent gains, outperforming the base models (+9.1 points in Macro F1), continual pretraining (+6.3), synthetic label generation (+12.5), as well as common baselines. The results show that relevance attribution can serve as a powerful source of supervision for decoder learning from unlabeled data, beyond existing methods.
Read the full abstract ▾
All authors Pietro Ferrazzi, Matteo Merler, Giovanni Bonetta, Alberto Lavelli, Bernardo Magnini
Computation and Language
Shiping Zhu, Yibo Yang, Zhengyang Wang et al. (+3 more)
Large
language model
agents are increasingly deployed in human-human interaction settings, such as meeting assistants and clinical documentation systems, where they must observe conversations and retain information for downstream queries. Unlike traditional human-assistant settings, these environments are inherently
multimodal, involve complex discourse phenomena such as anaphora and deixis, and contain asynchronous or conflicting information from multiple participants. However, existing
memory benchmarks largely focus on single-user, text-only interactions, failing to capture these challenges. To address this gap, we introduce H2HMem, a Human-to-Human
Multimodal Memory Benchmark for evaluating
memory capabilities in complex human-human interactions. H2HMem includes both dyadic and multi-party conversations with
multimodal information streams, and evaluates
agents along three dimensions:
memory recall,
reasoning, and application. Experiments with advanced
agents reveal substantial limitations in constructing, retaining, and utilizing
memories across modalities, participants, and sessions, highlighting substantial room for improvement in next-generation LLM
agents.
Read the full abstract ▾
All authors Shiping Zhu, Yibo Yang, Zhengyang Wang, Tiancheng Shen, Dandan Guo, Ming-Hsuan Yang
Computation and Language
AbstRAG: Learning to Abstract for Retrieval Problems
Lei Xu, Xin Quan, Daniel Pedronette et al. (+1 more)
Retrieval-augmented generation often fails when the query, the document evidence, and the user's intent are expressed at different levels of abstraction. A query may ask about a class, a relation, or an event, while the document only states specific instances, indirect framings, or scoped formulations. We define this mismatch as an abstraction gap: the minimal set of typed assumptions required to align query intent with the available evidence. To close this gap, we introduce AbstRAG, which treats abstraction as an explicit
retrieval object. AbstRAG decomposes the query–evidence gap into expression, conceptual, intent–evidence, and event-type components, and scores relevance by combining match quality, a query-independent utility prior, and the cost of the required bridges. Its central mechanism is reflective refinement: a critic diagnoses
retrieval failures, localizes the failed abstraction operator, proposes a minimal stage-specific patch, and accepts the patch only under sufficiency and compression controls. Across three within-document
retrieval benchmarks against seven baselines, AbstRAG outperforms on nDCG@10 in 18 of 21 paired-bootstrap contrasts and improves generation accuracy by 1.9%, 5.2%, and 4.0% across the three
benchmarks; ablations confirm that reflective refinement drives most of the
retrieval gain and the compression control alone reduces over-expansion false positives from 73.7% to 0% on a stress slice.
Read the full abstract ▾
All authors Lei Xu, Xin Quan, Daniel Pedronette, André Freitas
Computation and Language
Reasoning without Gold Standards: A Proxy-Judge Theory of Autoformalization
Lei Xu, Xin Quan and André Freitas
Autoformalization (AF) requires both prover acceptance and fidelity to an informal source, but prover acceptance alone cannot establish fidelity, and expert-validated reference formalizations are costly to obtain. We introduce a reference-free proxy-judge framework, which separates correctness into grounding, statement faithfulness, coverage, and inference, and a theory of how imperfect checks shape iterative refinement. We establish three results. First, for a fixed sequence of candidates, an added proxy's false-positive and false-negative rates bound its effect on the pass-but-wrong rate. Second, damage to a correct formalization requires a false rejection that exposes it to further refinement, and harmful revisions are then retained through unguarded changes, missed changes, or prover progress that overrides judge warnings. Third, a decomposition of the final pass rate distinguishes continued refinement, generation of new candidates, and their success in passing the checks. We instantiate the framework with eight proxies and test these predictions on ProofNet and miniF2F in Lean~4 and on e-SNLI and ProntoQA in Isabelle/HOL. Under single-proxy removal, no prediction written before the runs is contradicted, and all traced breaks follow the identified failure routes. The results connect proxy reliability to the benefits, risks, and limits of refinement without reference formalizations.
Read the full abstract ▾
Computation and Language
MUDIDI: A Two-Stage Framework for Multilingual Dictionary Digitization with Language Models
David Setiawan, Temuulen Khishigsuren, Milind Agarwal et al. (+3 more)
Multilingual dictionaries are among the most valuable documentary resources for low-resource and endangered
languages, yet many remain available only as scans. For many decades, their digitization and conversion into a machine-readable format was nearly impossible due to
language-specific scripts, complex multi-column layouts full of entries with abbreviations and cross-references. Recent
vision-
language models offer a promising solution, but it is unclear how well they preserve characters, markup, and process lexicographic structure. We introduce MUDIDI, a two-stage framework for multi-lingual dictionary digitization. Stage One evaluates the quality of character recognition and markup preservation; Stage Two focuses on dictionary entry
segmentation with subsequent mapping into a machine-readable lexicographic schema, SIL's Multi-Dictionary Formatter. We also release a
dataset that consists of human-annotated lexicographic entries collected from 30 public-domain dictionaries featuring diverse writing systems,
language families, and formats. We
benchmark OCR systems, general-purpose Large
Language Models (LLMs), and
Vision Language Models (VLMs) on the
dataset, demonstrating superior performance of LLMs across most writing systems and
languages in both stages, and provide practical guidelines on improving the results for more challenging scenarios. Finally, we show that supplementing additional information, such as dictionary introduction, to the LLMs can improve the quality of the digitized dictionary. Github: https://github.com/naarm-nlp/mudidi
Read the full abstract ▾
All authors David Setiawan, Temuulen Khishigsuren, Milind Agarwal, Pagnarith Pit, Aso Mahmudi, Ekaterina Vylomova
Computation and Language
Guide Me Out: A Framework to Benchmark VLM Operators Communication in Crisis Scenarios
Giacomo Gonella, Stefano Menini and Marco Guerini
Effective crisis response requires spatially grounded communication that bridges linguistic guidance of civilians with the physical environment, accounting for structural bottlenecks, evolving threats, and
agent-specific contexts. Yet, current NLP research in crisis communication remains mainly limited to static, text-only classification settings, overlooking the critical communicative role of AI operators in dynamic,
embodied scenarios. We address this gap with a novel benchmarking framework for evaluating
Vision-
Language Models (VLMs) tasked with guiding civilian
agents through simulated evacuations. We test two communication strategies (narrowcast vs. broadcast), two environment representations (visual vs. graph-based), and two threat behaviors (static vs. moving) across nine maps of varying structural complexity. Our results show that Narrowcast consistently reduces civilian Fail rates compared to Broadcast across all difficulty levels. Guidance quality depends heavily on how the VLM operator represents the world: the visual modality drives performance, while adding an adjacency graph is model-dependent and often harmful. Moving threats raise Fail rates across all conditions as communication must continuously adapt over time. Together, these findings show that deploying VLMs as AI operators in evacuation scenarios remains a non-trivial challenge, where the choice of communication strategy and input representation can directly determine the success or failure of the intervention.
Read the full abstract ▾
Computation and Language
Toward Signing Activity Projection in Sign Language Interaction
Takao Obi, Wang Yusong, Koji Inoue et al. (+1 more)
Social
robots must interact robustly not only with users assumed by
speech-centered systems but also with diverse users whose communication relies on different modalities, e.g., sign
language. One important capability gap is predictive turn-taking with signing users. Although Voice Activity Projection (VAP) has been successfully used to model future voice activity in spoken interaction, it remains unclear whether the framework transfers to sign
language interaction. This paper presents an initial transfer study of adapting a VAP architecture to dyadic sign
language interaction. Using interaction recordings from the Public DGS Corpus, we derive binary signing activity streams from lexical sign annotations and formulate proxy tasks for turn-taking prediction. The model uses pose-derived hand, eye-region, and mouth-region features extracted for each signer. The results show that SHIFT/HOLD prediction is promising, especially with hand cues, while SHIFT-prediction remains difficult. These findings provide initial evidence for both the promise and the current limitations of transferring predictive turn-taking models from spoken interaction to sign
language interaction. Predictive modeling of sign
language interaction still requires sign-
language-specific event definitions that go beyond
speech-derived categories.
Read the full abstract ▾
All authors Takao Obi, Wang Yusong, Koji Inoue, Kotaro Funakoshi
Computation and Language
What Should a Skill Remember? Quality–Cost Trade-offs in Cost-Aware Skill Rewriting for Language Model Agents
Qinghua Xing, Yinda Chen, Yaping Jin et al. (+6 more)
Large
language model
agents increasingly rely on skills: reusable procedural documents encoding workflows, tool use, implementation patterns, validation checks, and domain rules. Skill rewriting is often treated as
prompt compression, but shorter skills can make
agents more expensive by removing sparse operational anchors that prevent exploration, debugging, and recovery. We study skill rewriting through this economic lens. Our controlled framework profiles skill structure, rewrites skills using information-preservation strategies, and evaluates the rewrites under fixed task instructions, environments, and verifiers. Experiments on SkillsBench reveal distinct quality–cost trade-offs across strategies: API/code anchoring, workflow guarding, and rule/formula anchoring benefit different task families, with no universally dominant template. In the main held-out evaluation, the learned policy reduces total cost by 7.0% and downstream
agent-
token cost by 6.0%; in frozen cross-model transfer, the corresponding reductions average 14.7% and 13.7%, while verifier quality is preserved. These results position skill design as cost-aware operational knowledge engineering rather than
prompt compression. Resources: https://github.com/1Reminding/Skill_EE.
Read the full abstract ▾
All authors Qinghua Xing, Yinda Chen, Yaping Jin, Zhenhe Wu, Bohan Lin, Hang Zhou, Xinghao Chen, Hanting Chen, Zhiwei Xiong