skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Award ID(s):
2211972 2228287
PAR ID:
10532814
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
ACM
Date Published:
ISSN:
2000-5467
ISBN:
9798400703836
Page Range / eLocation ID:
24 to 35
Format(s):
Medium: X
Location:
Vancouver BC Canada
Sponsoring Org:
National Science Foundation
More Like this
  1. Large language models (LLMs) demonstrate surprising capabilities, but we do not understand how they are implemented. One hypothesis suggests that these capabilities are primarily executed by small subnetworks within the LLM, known as circuits. Identifying these circuits is particularly useful in the context of building models that are robust to shortcut learning and distribution shifts. Identifying these shortcut encoding circuits allows us to "turn them off" by replacing their outputs with random values or zeros. Many papers have claimed to identify meaningful circuits in existing language models. In this paper, we focus on evaluating candidate circuits. Specifically, we formalize a set of criteria that a circuit is hypothesized to meet and develop a suite of hypothesis tests to evaluate how well circuits satisfy them. The criteria focus on the extent to which the LLM's behavior is preserved, the degree of localization of this behavior, and whether the circuit is minimal. We apply these tests to six circuits described in the research literature. We find that synthetic circuits -- circuits that are hard-coded in the model -- align with the idealized properties. Circuits discovered in Transformer models satisfy the criteria to varying degrees. To facilitate future empirical studies of circuits, we created the circuitry package, a wrapper around the TransformerLens library, which abstracts away lower-level manipulations of hooks and activations. The software is available at https://github.com/blei-lab/circuitry. 
    more » « less
  2. null (Ed.)
    Matriliny is a system of kinship in which descent and inheritance are conferred along the female line. The theoretically influential concept of the matrilineal puzzle posits that matriliny poses special problems for understanding men's roles in matrilineal societies. Ethnographic work describes the puzzle as the tension experienced by men between the desire to exert control over their natal kin (i.e. the lineage to which they belong) and over their affinal kin (i.e. their spouses and their biological children). Evolutionary work frames the paradox as one resulting from a man investing in his nieces and nephews at the expense of his own biological offspring. In both cases, the rationale for the puzzle rests on two fundamental assumptions: (i) that men are in positions of authority over women and over resources; and (ii) that men are interested in the outcomes of parenting. In this paper, we posit a novel hypothesis that suggests that certain ecological conditions render men expendable within local kinship configurations, nullifying the above assumptions. This arises when (i) women, without significant assistance from men, are capable of meeting the subsistence needs of their families; and (ii) men have little to gain from parental investment in children. We conclude that the expendable male hypothesis may explain the evolution of matriliny in numerous cases, and by noting that female-centred approaches that call into doubt assumptions inherent to male-centred models of kinship are justified in evolutionary perspective. This article is part of the theme issue ‘The evolution of female-biased kinship in humans and other mammals’. 
    more » « less