CS Paper Radar

Weekly top 20

2026-W35 Aug 24 – Aug 30, 2026

Ranked from 3,938 papers submitted on 7 days. Each research area gets slots in proportion to its share of this week's papers (at least one), filled by score; near-duplicates are removed. Why

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works
1

A Unified Framework to Elicit Structured Feedback for Interpretable Multi-Trait Essay Scoring

cs.CL ·2026-08-28 ·Shihang Yang, Sanwoo Lee, Ningning Zhao, Yunfang Wu
top venuecode/datahot direction
Abstract · 14 pages, accepted to EMNLP 2026 Findings. Code: https://github.com/Atiyahsama/HiFTS

Multi-trait Automated Essay Scoring (AES) requires rubric-grounded reasoning across interdependent traits, rather than isolated score prediction. Existing feedback-enhanced methods often decouple feedback from scoring or assess traits independently, weakening score--feedback consistency and rubric alignment. We propose HiFTS, a unified autoregressive framework that generates hierarchical CoT feedback before predicting trait-level and holistic scores. HiFTS distills rubric-grounded hierarchical CoT feedback from a teacher LLM and trains student models to jointly generate feedback and scores. HiFTS further applies Group Relative Policy Optimization with a composite reward balancing score agreement, calibration, feedback quality, and structural validity. At inference, a lightweight global prior provides holistic guidance to reduce drift during long-form reasoning. We also introduce CFMS-34, a Chinese multi-trait AES dataset with 951 essays annotated with holistic scores and 34 rubric-based traits. Experiments on CFMS-34 and ASAP++ show that HiFTS achieves strong holistic and trait-level scoring while producing coherent, rubric-aligned feedback.

0.90
2

The Hallucination Signal Is a Mean Shift: Why Simple Probes Suffice

cs.CL cs.AIcs.LG ·2026-08-28 ·Jungseob Lee, Jaehyung Seo, Heuiseok Lim
top venuecode/data
Abstract · 19 pages, 7 figures, 20 tables. Accepted to EMNLP 2026 (Main Conference). Code: https://github.com/js-lee-AI/LayerMix

Hidden-state probes effectively detect LLM hallucinations, but the geometry of the signal remains poorly characterized, driving increasingly complex probe architectures. Across three 7B-scale models and three datasets in a paired-example paradigm, we find the signal overwhelmingly dominated by a single mean-shift component, and removing this direction collapses detection to chance. Shrinkage linear discriminant analysis closes about 73% of the gap between 1D and full-dimensional classifiers, so apparent architectural complexity largely reflects high-dimensional covariance estimation difficulty rather than exploitable non-linearity. A simple L2-regularized logistic regression (0.952 AUROC) bounds or outperforms twelve controlled architectural alternatives, and our multi-layer aggregation exceeds CLAP cross-layer attention probing under matched paradigm. Because the signal spans a contiguous layer band, LayerMix aggregates it to match oracle-layer performance without oracle access. Our claims characterize the geometry within the controlled paired-example paradigm. Our code is available at https://github.com/js-lee-AI/LayerMix.

0.90
3

Which Metrics Save the Most Human Annotation? Prediction-Powered Evaluation and Meta-Evaluation

cs.CL stat.ML ·2026-08-27 ·Mingqi Gao, Anthony Sicilia, Weiyan Shi
top venuecode/data
Abstract · Accepted at EMNLP 2026 (Main). Code available: https://github.com/CHATS-lab/ppi-eval

Across various non-verifiable tasks, human evaluation is reliable but expensive, while automatic metrics are more scalable but often biased. Building on prediction-powered inference (PPI), we propose prediction-powered evaluation, a framework that combines limited human judgments with large-scale automatic scores to obtain data-efficient system comparisons that are provably unbiased. We develop parametric and non-parametric procedures, analyze the efficiency trade-off between paired and unpaired designs, and validate the framework on six WMT datasets. We further introduce the Prediction-Powered Saving Ratio (PPSR), a meta-metric that measures how much human annotation an automatic metric can save when used within prediction-powered evaluation. PPSR directly targets metric utility for prediction-powered evaluation and yields more discriminative and stable metric rankings than existing system-level meta-metrics. Overall, our new paradigm reframes automatic metrics as tools for reducing human annotation cost rather than replacing human judgment, and applies broadly to non-verifiable tasks.

0.84
4

QUORUM: QUality-Optimized Routing Using Multiple annotators

cs.CL ·2026-08-28 ·Antonio Purificato, Maria Sofia Bucarelli, Andrea Bacciu, Amin Mantrach, Fabrizio Silvestri
top venuecode/data
Abstract · 4 figures, 18 pages

Data annotation remains a central bottleneck in natural language processing, requiring human effort to obtain high-quality labels at scale. While Large Language Models (LLMs) offer a fast and cost-effective alternative, their reliability is highly instance-dependent: they perform well on simple inputs but often fail on examples requiring nuanced reasoning or contextual understanding. In this work, we address this challenge with QUORUM (QUality-Optimized Routing Using Multiple annotators), a budget-aware routing framework that dynamically assigns each instance to human or LLM annotators under a fixed annotation budget. Unlike prior approaches relying on model confidence or uncertainty estimates, QUORUM leverages feature-based signals to estimate instance difficulty and supports multiple annotations per instance, combining them through agreement-based rewards to improve reliability. We evaluate QUORUM across diverse closed- and open-ended annotation tasks in English and multilingual settings, and QUORUM improves annotation quality by up to 34.4% while reducing costs by 8.8% over competing methods. Code can be found at https://github.com/amazon-science/QUORUM.

0.84
5

XQDT: eXplainable and Quantitative Data-Text Alignment Metric with Feedback Signals

cs.CL ·2026-08-30 ·Kun Efimov-Zhang, Yifei Song, Claire Gardent
top venuecode/datahot direction
Abstract · Accepted to EMNLP 2026 (Main Conference)

Evaluating data-text alignment remains challenging: existing metrics often provide limited explanations for the scores, while prompt-based LLM-as-Judge methods can be expensive and unreliable. We present an end-to-end explainable evaluation metric that fine-tunes a language model to identify omitted, extra, incorrect, and correct data units in a data-text pair. These local judgements are aggregated into precision, recall, and F1 scores, providing both fine-grained diagnostic feedback and an interpretable measure of alignment quality. Across benchmarks, our fine-tuned models outperform LLM-as-Judge methods in error prediction and achieve competitive precision, recall, and F1 scores, while maintaining strong correlation with human judgements. Beyond evaluation, our verifier outputs also provide useful feedback signals for downstream correction and refinement, supporting alignment-oriented improvement of data-to-text and text-to-data. Code and resources are available at https://github.com/guihuzhang/xqdt.

0.83
6

Phoneme- and Word-Level Metrics Using Self-Supervised Speech Representations for Forced Alignment Evaluation

cs.CL ·2026-08-28 ·V. S. D. S. Mahesh Akavarapu, Michael Daniel, Gerhard Jäger
top venuecode/data
Abstract · Accepted at EMNLP-2026 (Findings)

Forced alignment evaluation typically requires manually annotated timestamps, limiting large-scale and multilingual analysis. We introduce two corpus-level metrics based on self-supervised (SSL) speech representations for reference-free forced alignment evaluation: Phoneme-Cluster Mutual Information (PCMI) and Word Acoustic Consistency Score (WACS). PCMI measures agreement between aligned phoneme labels and clusters induced from SSL-speech representations, while WACS measures consistency of repeated word realizations using dynamic time warping similarity between word representation sequences. Using both random and systematic perturbations, we show that PCMI and WACS degrade consistently under alignment perturbations. We further analyze the metrics across multiple alignment systems on 85 languages from FLEURS, validate them against manually annotated alignments from 45 languages in DoReCo, and evaluate them on two phonologically complex low-resource languages. The metrics effectively separate high- and low-quality alignments and correlate strongly with timestamp-based alignment quality measures. Our results demonstrate that SSL-speech representations enable scalable, reference-free forced alignment evaluation. The metrics are available as an open-source Python package at https://github.com/mahesh-ak/forced-aligner-metrics.

0.82
7

Linear Probing Provides Robust and Efficient Detection of Machine-Generated Text

cs.CL ·2026-08-25 ·Gerrit Quaremba, Hanqi Yan, Elizabeth Black, Denny Vrandecic, Elena Simperl
top venuecode/data
Abstract

Distinguishing machine-generated text (MGT) from human-written text (HWT) becomes increasingly important due to potential misuse. However, most supervised detectors often degrade out-of-domain (OOD) and require large, diverse training sets. In this work, we analyze the linearity and quality of MGT representations and show that simple linear probes outperform a wide range of detectors while being substantially more sample-efficient. We first show that MGT and HWT latent representations are linearly separable in low-dimensional space, and provide a plausible explanation for this separability through systematic differences in their representation quality. Motivated by these insights, we train two variants of simple linear probes and evaluate them across 4 benchmarks against 16 baselines. Probes consistently improve OOD detection (+11 AUC), requiring solely ${<}100$ samples to reach near-peak performance. We show that this transferability arises because probes recover a shared latent MGT direction that generalizes across diverse settings. Finally, we demonstrate that probing vectors capture a continuous spectrum of ``machineness'', highlighting their potential for fine-grained estimation of AI-edited text. Overall, our work provides insights into latent-space differences between MGT and HWT and demonstrates the potential of linear probes as as robust and sample-efficient MGT detectors. We release our code on~\href{https://github.com/gerritq/mgt_probes}{github}.

0.82
8

AffectOmni: RL-Verifiable People-Centric Grounded Affective Reasoning for Social and Art-Related Scenes

cs.AI ·2026-08-24 ·Yibo Wang, Rui Yang, Jisheng Dang, Bimei Wang, Yitao Wu +5 more
top venuecode/data
Abstract · 12 pages, 5 figures

Multimodal large language models (MLLMs) achieve strong performance on VQA and scene understanding, yet affective reasoning remains vulnerable to shortcut behavior. Models may predict correct answers while neglecting people-centric cues such as micro expressions and body language, which weakens traceability and external verification. Prior reinforcement learning approaches mainly reward context or logical coherence without explicitly enforcing attention to human evidence. In addition, LLM as a Judge scoring often suffers from score clustering, which reduces reward discriminability. We propose AffectOmni, a GRPO trained framework for verifiable affective reasoning. AffectOmni introduces People Focus and Temporal Order rewards to encourage people-centric evidence selection and temporally structured reasoning, and it adopts within-group comparative scoring to produce more stable and discriminative reward signals. For verification, a Thinking Summarizer converts free form rationales into executable evidence instructions, which are grounded into pixel level evidence regions via SAM3 to provide an externally auditable interface outside the training loop. Experiments on IntentBench, Daily Omni, and WorldSense show consistent improvements over open source 7B scale baselines, including gains of 4.66% on emotion recognition and +14.29% on temporally sensitive tasks. Code is available at https://github.com/eliot127825-rgb/AffectOmni_nobody.

0.80
9

Model predictive traction control system based on the Koopman operator

eess.SY ·2026-08-26 ·Josip Kir Hromatko, Šandor Ileš
publishedcode/data
Abstract · 6 pages, 4 figures; associated code available at https://github.com/PVDC-project/pvdc-kmpc-traction-control

Due to their importance, traction control and anti-lock braking systems have become standard equipment in modern vehicles. However, accurate models of tire dynamics are often difficult to obtain and usually include nonlinearities, making their use in control systems challenging. This paper describes a traction control system based on model predictive control and Koopman operator theory, which aims to approximate nonlinear systems with linear ones through a state space transformation. A linear model predictive controller based on the Koopman predictor is compared to a standard nonlinear model predictive controller. Experiments in a high-fidelity vehicle dynamics simulation environment show a comparable reference tracking performance of the two controllers, with a reduced execution time for the proposed Koopman operator-based algorithm, both on a standard PC and embedded hardware.

0.78
10

TailorCoPilot: Enabling Agentic Pattern Making with Version-Controlled State Tracking

cs.HC cs.GR ·2026-08-26 ·Yuexin Sun, Zhaohui Wang, Ruiyang Liu, Demian Kong, Qian He +2 more
top venuecode/datahot direction
Abstract · To appear in ACM Symposium on User Interface Software and Technology (UIST 2026); Project page: https://fox2049.github.io/tailorcopilot/

Experience-driven manufacturing, such as garment pattern making, faces a severe generational skills gap because its core expertise relies on undocumented tacit knowledge forged through day-to-day practice. To address this challenge, we present TailorCoPilot, an agentic pattern-making system built upon a specially designed version-control backend TailorTrace. TailorTrace models sewing patterns as structured, discrete states and records their transformations during the pattern-making process as explicit operation sequences defined upon the geometry primitives in the sewing pattern (panels, edges, vertices and stitches). Integrated into a conventional pattern-making GUI, TailorTrace enables seamless documentation of senior experts' tacit pattern-making knowledge without breaking their daily workflow. The documented knowledge further offers interactive, pedagogical scaffolding for novices, while providing a robust foundation to power TailorCoPilot and train future generative AI models. In a user study with novices and advanced novices, TailorCoPilot improved task completion rates, reduced time and perceived workload, and yielded higher-quality artifacts compared to skill-appropriate baselines. Ultimately, TailorCoPilot demonstrates a viable pathway to capture practice-based expertise, operationalizing it to support both generative AI advancements and human apprenticeship.

0.77
11

When 3D Gaussian Splatting Recovers Real Surfaces

cs.LG cs.CV ·2026-08-30 ·Songhe Wang, David Johnathan Miller
top venuetheory
Abstract · Accepted at ECCV 2026. 30 pages, 3 figures, 1 table; includes supplementary material

When does 3D Gaussian Splatting (3DGS) recover the true scene surface rather than just overfitting view-dependent appearance? We answer this by developing a mathematical framework based on a first-hit rendering abstraction that cleanly isolates geometry from appearance. We prove that geometric misalignment forcefully converts spatial textures into high-frequency angular signals via parallax. This establishes a strict identifiability window: if angular capacity is bounded, surface-consistent solutions are mathematically preferred; if unrestricted, the same images can be perfectly explained by an incorrect, opaque billboard geometry. Experiments on synthetic stress tests confirm this prediction, showing billboard failures emerge precisely at high angular capacities. Conversely, in the real-world datasets we evaluate under standard capture protocols, reconstructions remain surface-consistent even at high SH degrees, which is consistent with the prediction that rich spatial texture can push billboard solutions outside the tested angular-capacity range.

0.77
12

MoPLEx: Estimating Plackett-Luce Mixture Models for Multi-Objective Alignment

cs.LG cs.AIcs.CL ·2026-08-25 ·Dongyue Li, Ziniu Zhang, Lu Wang, Hongyang R. Zhang
top venuehot direction
Abstract · 19 pages; To appear in EMNLP 2026

We study learning a mixture of $k$ Plackett-Luce models from multi-way ranking responses from annotators that may represent heterogeneous underlying preferences. This problem has many applications in AI alignment and preference optimization. Prior work has studied mixtures of Bradley-Terry models from pairwise comparisons. However, estimating a mixture of multi-way ranking models can become theoretically unidentifiable when $k$ exceeds $m/2$, where $m$ is the ranking length. We design an efficient algorithm to address this issue by first augmenting the rankings to a larger size (e.g., generating comparisons from a base model), followed by a gradient-based estimation to reduce inference cost (in the input embedding space). With this procedure in mind, we then fit a mixture of Plackett-Luce (PL) models via an expectation-maximization-style iteration, or MoPLEx in short. We conduct extensive experiments to verify this algorithm. First, we find that the gradient-based approximation estimates true probabilities with less than 5% error on models with up to 34 billion parameters. Second, MoPLEx improves clustering and ranking accuracy by an average of 43.7% and 15.2% over baselines using a single PL model or a mixture of Bradley-Terry models, on UltraFeedback and PERSONA datasets. These results demonstrate the effectiveness of MoPLEx for tackling multi-way rankings following heterogeneous preferences through measuring alignment via gradients.

0.76
13

SA-Bench: Evaluating Semantic Alignment in LLM-Based Paper Reproduction

cs.AI cs.SE ·2026-08-25 ·Xue Hu, Zewei Pan, Zeli Su, Zhou Liu, Wentao Zhang
top venuebenchmarkcode/data
Abstract · Accepted to Findings of EMNLP 2026

LLM agents can generate paper reproduction code, yet often produce scientifically unfaithful implementations. We define this failure mode as semantic drift, where generated code silently diverges from the paper's specifications. We introduce SemanticAlign-Bench(SA-Bench), a diagnostic benchmark covering 30 papers from ICLR, ICML and NeurIPS 2025. For each paper, we decompose its specifications into atomic and verifiable implementation claims, which we call Semantic Alignment Units (SAUs) and evaluate repositories along four diagnostic dimensions spanning numerical, methodological, protocol and ordering drift. In total, we construct 1,491 SAUs across five ML domains and evaluate 12 generator configurations (4 models $\times$ 3 scaffolds). Even the strongest configuration (Claude+PaperCoder) achieves a mean SAU score of only 0.301 out of 1.0, with an overall mean of 0.221 across 360 evaluations. A failure taxonomy reveals that agents attempt most requirements but implement them incorrectly, with implementation mismatch and stubs accounting for the majority of zero-scored claims. Our analysis further indicates that scaffolds optimized for executability provide limited leverage for scientific reproduction; narrowing the gap requires scaffolds that prioritize semantic specification verification. The benchmark, annotations and evaluation pipeline are publicly available.

0.75
14

On the Resilience of Text-to-Video Diffusion Models to Hardware Faults

cs.LG ·2026-08-30 ·Zachary Coalson, A M Aahad, Stella Doehring, Zane Ma, Sanghyun Hong
publishedbenchmarkcode/datahot direction
Abstract · Accepted to ICML 2026 Workshop on From Frames to Stories (F2S)

We present the first systematic study of the resilience of text-to-video (T2V) diffusion models under random hardware-level faults. While T2V models are widely used for automated video generation due to their ability to produce high-quality, temporally coherent, and realistic videos, their iterative denoising process and spatiotemporal dependencies introduce unique failure modes. We perform an extensive fault-injection study covering both computational and memory faults across three T2V models and a representative benchmark. Our results show that (1) a single fault can degrade overall performance by up to 3.7\%, with semantic correctness more affected than perceptual quality; (2) memory faults are more damaging than computational faults, high-order exponent bits are particularly vulnerable, and the widely-used bfloat16 is more susceptible than alternative formats; and (3) 7-28\% of faults cause visible artifacts, including semantic changes such as added objects, suggesting that single faults are sufficient to alter output semantics. Our findings reveal reliability risks in deployed T2V systems and motivate further research on improving fault resilience. Code: \href{https://github.com/ztcoalson/T2V-Resilience}{https://github.com/ztcoalson/T2V-Resilience}.

0.75
15

Study of Resistive Switching Dynamics and Memory States Equilibria in Analog Filamentary Conductive-Metal-Oxide/HfOx ReRAM via Compact Modeling

cs.ET ·2026-08-26 ·Matteo Galetta, Donato Francesco Falcone, Victoria Clerico, Wooseok Choi, Stephan Menzel +5 more
publishedhighly cited
Abstract

Resistive Random Access Memory (ReRAM) devices offer a promising solution for next-generation non-volatile memory and neuromorphic computing systems. Yet, existing compact models fail to capture analog resistive switching behavior of ReRAM devices. This work presents an advanced physics-based compact model for analog filamentary Conductive-Metal-Oxide (CMO)/HfOx ReRAM, capable of reproducing switching characteristics over a broad range of operating conditions. Compared to the state-of-the-art, the model extends the dynamic interplay between ion migration and electron hopping, while also accounting for parasitic resistive elements. Simulations of various voltage inputs are tested to reproduce quasi-static I-V curves, SET switching kinetics under single-pulse programming conditions, and analog accumulative conductance modulation upon bipolar identical pulse streams. Additional simulations reveal the physical criterion underlying the stabilization of the CMO/HfOx-based ReRAM memory state around the equilibrium point, namely symmetry point, under pulsing conditions when a fading memory mechanism emerges. Building upon the evidence of such equilibrium stabilization under pulsing and quasi-static conditions, a procedure is established to visualize and map equilibrium memory states across different input domains. The physical model supports design optimization of switching behavior for analog neuromorphic systems and non-volatile memory architectures. It also enables accurate integrated circuit simulations with CMO/HfOx-based ReRAM technology.

0.74
16

Right Diagnoses, Decorative Reasoning:A Perturbation Audit of Medical Chain-of-Thought

cs.AI ·2026-08-25 ·Mengzhu Xu, Jifan Gao, Xia Jiang, Yaoxin Wu, Xi Long
top venue
Abstract

Clinicians read chain-of-thought (CoT) rationales as evidence of medical reasoning, but whether the visible chain plays that role is rarely tested. General-domain CoT-faithfulness probes ignore clinical cost, and medical LLM evaluations treat the chain as a black box. We close this gap with a medical perturbation audit: a 30-operator battery edits both the chain and the question with clinically motivated operators (severity reversal, negation flip, demographic swap, evidence ablation), paired with a chain-update times answer-flip joint analysis that classifies each model by its failure mode. Applied to 14 LLMs on four medical QA benchmarks, three independent tests converge: the Chain-Decoupling Rate (CDR; chain does not register the edit and the answer does not flip) is 72.9% panel-wide on clinically meaningful destructive edits, chain corruption leaves accuracy unchanged, and removing CoT prompting does not reduce accuracy. Two board-certified clinicians re-annotate N=197 perturbed questions; 98.5% leave the gold defensible. The pattern holds across medical and reasoning fine-tuning and scale; on the closed-source tier, where the chain text is unavailable, the answer-side signals are consistent with the same decoupling. Our framework and CDR provide a reusable yardstick for auditing whether medical CoT is faithful or merely documentation.

0.74
17

Data-Driven Dimension Reduction for Industrial Load Modeling Using Inverse Optimization

eess.SY ·2026-08-25 ·Ruike Lyu, Hongye Guo, Goran Strbac, Chongqing Kang
top venuehighly cited
Abstract · Manuscript accepted by IEEE Power Engineering Letters (Published in: IEEE Transactions on Smart Grid ( Volume: 16, Issue: 3, May 2025))

The intricate mixed-integer constraints in industrial load models not only pose challenges for their direct integration into economic dispatch or market clearing processes but also render current analytical dimension-reduction methods ineffective. We propose a novel data-driven dimension-reduction approach for industrial load modeling, which uses the optimal energy usage data from industrial loads to train a dimension-reduced model that best fits the original constraints. Our approach, implemented by the adjustable load fleet model, outperformed analytical methods across three industrial load datasets.

0.74
18

The Value Generating Power of Weighted Tree Automata with Initial Algebra Semantics

cs.FL ·2026-08-25 ·Manfred Droste, Zoltán Fülöp, Andreja Tepavčević, Heiko Vogler
published
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the generating power of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings) and the question under which conditions the weighted tree automata can produce only finitely many values. We show that there exists a right-distributive strong bimonoid which is bi-locally finite but not locally finite. We also show that if the ranked alphabet contains a symbol with rank at least two, then for any finitely generated strong bimonoid, weighted tree automata can generate, via their initial algebra semantics, all elements of the strong bimonoid. As a consequence of these results, for bi-locally finite right-distributive strong bimonoids which are not locally finite, weighted tree automata can generate infinitely many values, provided that the input ranked alphabet contains a symbol with rank at least two. This is in sharp contrast to the setting of weighted string automata, which can generate only finitely many values. As a further consequence, for any finitely generated semiring, there exists a weighted tree automaton which generates, via its run semantics, all elements of the semiring.

0.72
19

A Comprehensive Survey on Linguistic Steganography: Methods, Countermeasures, Evaluation, and Challenges

cs.CR cs.CL ·2026-08-29 ·Ruiyi Yan, Chenhui Chu, Zhongliang Yang, Yugo Murawaki
top venuesurveyhighly cited
Abstract · Accepted by EMNLP 2026

Linguistic steganography hides secret messages in natural language text. Large language models (LLMs) have reshaped the field, but a systematic account of how these scattered advances collectively reshape the field in this new era is still missing. We provide one along four axes: 148 steganographic methods, 60 linguistic steganalysis countermeasures, 23 evaluation metrics, and 9 open challenges, each with taxonomies, reviews, and adoption analyses. Cutting across these axes, we identify five specific paradigm shifts in the LLM era: (1) from covertext modification to prompt-only generation, (2) from heuristic to provable security, (3) from white-box symmetric LMs to black-box or asymmetric access, (4) from security-centric designs to joint optimization, and (5) from text-quality concerns to engineering issues. The survey aims to serve as both a reference and a roadmap for practical and responsible linguistic steganography in the LLM era.

0.72
20

Beyond the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-28 ·Nima Anari
theorycode/data
Abstract · 34 pages. Accompanying Lean 4 formalization: https://github.com/nimaanari/formalization-beyond-bethe. Palomar Registry entry: https://paloma…

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

0.67