Exact Paired-Permutation Testing for Structured Test Statistics (2022.naacl-main)
Copied to clipboard
| Challenge: | Existing methods to evaluate test statistic are Monte Carlo approximations which use a summation over all 2 N possible swaps. |
| Approach: | They propose an exact algorithm for the paired-permutation test for a family of structured test statistics. |
| Outcome: | The proposed algorithm is 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset. |
Similar Papers
Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers (N18-2)
Copied to clipboard
| Challenge: | Non-projective dependency trees account for 12.59% of all training sentences in the annotated Universal Dependencies (UD) 2.1 data. |
| Approach: | They generalize Cohen et al.'s (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference. |
| Outcome: | The proposed system can be extended to include a variant that reduces time complexity to O(n6), improving over the known bounds in exact inference for non-projective transition-based parsing. |
Accurate and Efficient Statistical Testing for Word Semantic Breadth (2026.acl-long)
Copied to clipboard
| Challenge: | Existing studies on semantic breadth and spread of words have focused on semantic relatedness, but contextualized token embeddings can be misleading. |
| Approach: | They propose a Householder-aligned permutation test to isolate dispersion differences from directional differences. |
| Outcome: | The proposed method reduces Type-I error by 32.5% while preserving sensitivity to genuine breadth differences. |
Synthetic Data Made to Order: The Case of Parsing (D18-1)
Copied to clipboard
| Challenge: | supervised dependency parsing is a core task in natural language processing, but unsupervised parsers can hardly produce useful parses. |
| Approach: | They propose to permute the constituents of an existing dependency treebank so that its surface part-of-speech statistics approximately match those of the target language. |
| Outcome: | The proposed method improves the parsing accuracy of a target language . the proposed method is based on a distribution of gold POS bigrams . |
When data permutations are pathological: the case of neural natural language inference (D18-1)
Copied to clipboard
| Challenge: | Recent research indicates that these datasets are trivially annotated to a large degree. |
| Approach: | They propose to use a trending NLP task to test a neural architecture for NLI . they show a pathological sensitivity of the systems to permutations of the training set . |
| Outcome: | The proposed model outperforms the baseline model by multiple percentage points . the proposed model is based on the proposed dataset and the soundness of the task . |
NLPStatTest: A Toolkit for Comparing NLP System Performance (2020.aacl-demo)
Copied to clipboard
| Challenge: | Statistical significance testing is used to compare NLP system performance, but p-values alone are insufficient because statistical significance differs from practical significance. |
| Approach: | They propose a three-stage procedure for comparing NLP system performance and a toolkit that automates the process. |
| Outcome: | The proposed procedure is based on a three-stage procedure and compares it with existing statistical testing toolkits. |
Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching (2025.acl-short)
Copied to clipboard
Juan Wisznia, Cecilia Bolaños, Juan Tollo, Giovanni Franco Gabriel Marraffini, Agustín Andrés Gianolini, Noe Fabian Hsueh, Luciano Del Corro
| Challenge: | a new framework for analyzing sorting algorithms in pairwise ranking prompting (PRP) is developed to re-center the cost model around LLM inferences rather than traditional pairwise comparisons. |
| Approach: | They propose a framework for analyzing sorting algorithms in pairwise ranking prompting (PRP) they propose to re-center the cost model around LLM inferences rather than traditional pairwise comparisons. |
| Outcome: | The proposed framework encourages strategies such as batching and caching to mitigate inference costs. |
Benchmarking Approximate Inference Methods for Neural Structured Prediction (N19-1)
Copied to clipboard
| Challenge: | Structured prediction models often involve complex inference problems for which finding exact solutions is intractable. |
| Approach: | They propose to perform gradient descent with respect to the output structure directly and train a neural network to perform inference. |
| Outcome: | The proposed methods achieve better speed/accuracy/search error trade-off than gradient descent while being faster than exact inference at similar accuracy levels. |
Entropy-Gated Branching for Efficient Test-Time Reasoning (2026.eacl-long)
Copied to clipboard
| Challenge: | Empirical results show that branching at low uncertainty points can improve reasoning capabilities of large language models . however, these methods require substantially more computational resources, causing errors in high-stakes domains . |
| Approach: | They propose an inference technique that selectively expands prediction sequences at points of high uncertainty. |
| Outcome: | Empirical results show that the proposed method improves accuracy by 22.6% over standard inference while operating 31%-75% faster across math benchmarks. |
Ranking Reasoning LLMs under Test-Time Scaling (2026.acl-long)
Copied to clipboard
| Challenge: | Large language models (LLMs) are increasingly used as general-purpose reasoning systems for tasks such as programming and mathematical problem solving. |
| Approach: | They formalize dense benchmark ranking under test-time scaling and introduce a library that implements statistical ranking methods such as paired-comparison models, item response theory, voting rules, graph- and spectral-based methods. |
| Outcome: | The proposed method is based on paired-comparison models, item response theory (IRT) models, voting rules, graph- and spectral-based methods. |
Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation (2022.findings-emnlp)
Copied to clipboard
| Challenge: | Existing approaches to generalize compositionally are inadequate, but there is no evidence for this. |
| Approach: | They propose a model-agnostic algorithm for subsampling instances with diverse structures from a labeled instance pool with structured outputs. |
| Outcome: | The proposed algorithm leads to comparable or better generalization than prior algorithms in 9 out of 10 dataset-split type pairs. |