Search

We develop a new, powerful method for counting elements in a multiset. As a first application, we use this algorithm to study the number of occurrences of patterns in a permutation. For patterns of length 3 there are two Wilf classes, and the general behaviour of these is reasonably well-known. We slightly extend some of the known results in that case, and exhaustively study the case of patterns of length 4, about which there is little previous knowledge. For such patterns, there are seven Wilf classes, and based on extensive enumerations and careful series analysis, we have conjectured the asymptotic behaviour for all classes., Comment: 32 pages. Updated references from previous version. Removal on earlier discussion of Stieltjes sequences, which was incomplete and confusing

Building a theoretical understanding of the capabilities of large language models (LLMs) is vital for our ability to predict and explain the behavior of these systems. Here, we investigate the structure of LLM capabilities by extracting latent capabilities from patterns of individual differences across a varied population of LLMs. Using a combination of Bayesian and frequentist factor analysis, we analyzed data from 29 different LLMs across 27 cognitive tasks. We found evidence that LLM capabilities are not monolithic. Instead, they are better explained by three well-delineated factors that represent reasoning, comprehension and core language modeling. Moreover, we found that these three factors can explain a high proportion of the variance in model performance. These results reveal a consistent structure in the capabilities of different LLMs and demonstrate the multifaceted nature of these capabilities. We also found that the three abilities show different relationships to model properties such as model size and instruction tuning. These patterns help refine our understanding of scaling laws and indicate that changes to a model that improve one ability might simultaneously impair others. Based on these findings, we suggest that benchmarks could be streamlined by focusing on tasks that tap into each broad model ability., Comment: 10 pages, 3 figures + references and appendices, for data and analysis code see https://github.com/RyanBurnell/revealing-LLM-capabilities

Many algorithms have been developed for enumerating various combinatorial objects in time exponentially less than the number of objects. Two common classes of algorithms are dynamic programming and the transfer matrix method. This paper covers the design and implementation of such algorithms. A host of general techniques for improving efficiency are described. Three quite different example problems are used for examples: 1324 pattern avoiding permutations, three-dimensional polycubes, and two-dimensional directed animals. For those new to the field, this paper is designed to be an introduction to many of the tricks for producing efficient enumeration algorithms. For those more experienced, it will hopefully help them understand the interrelationship and implications of a variety of techniques, many or most of which will be familiar. The author certainly found his understanding improved as a result of writing this paper.

We give an improved algorithm for counting the number of $1324$-avoiding permutations, resulting in 5 further terms of the generating function. We analyse the known coefficients and find compelling evidence that unlike other classical length-4 pattern-avoiding permutations, the generating function in this case does not have an algebraic singularity. Rather, the number of 1324-avoiding permutations of length $n$ behaves as $$B\cdot \mu^n \cdot \mu_1^{n^{\sigma}} \cdot n^g.$$ We estimate $\mu=11.60 \pm 0.01,$ $\sigma=1/2,$ $\mu_1 = 0.0398 \pm 0.0010,$ $g = -1.1 \pm 0.2$ and $B =9.5 \pm 1.0.$, Comment: 20 pages, 10 figures