Skip to content

METHODOLOGY.md

Latest commit

 

History

History
570 lines (374 loc) · 22.2 KB

METHODOLOGY.md

File metadata and controls

570 lines (374 loc) · 22.2 KB
Raw

HaystackBench — Evaluation Methodology

Version: 1.0 Last Updated: 2025-01-01

1. Introduction

This document provides a researcher-grade description of the evaluation methodology used by HaystackBench. It covers the mathematical formulations, implementation details, known biases, and guidance for interpreting results.

The Needle in a Haystack (NIAH) family of tests was introduced by Gregory Kamradt (2023) and subsequently expanded by researchers at BAAI (NeedleBench, 2024). HaystackBench implements and extends this test family.

2. Core Concepts

2.1 Notation

Symbol Definition
$L$ Context length in tokens
$d$ Needle depth as a proportion in $[0, 1]$
$N$ Number of needles in M-RT/M-RS tasks
$H$ Haystack document
$n_i$ The $i$-th needle
$q$ Query prompt
$r$ Model response
$s(r, n)$ Scoring function; returns score in $[0, 1]$

2.2 Document Construction

Given a haystack $H$ of total token length $|H|_T$ and a needle $n$ to insert at depth $d$:

  1. Compute insertion token position: $p = \lfloor d \cdot L \rfloor$
  2. Find the nearest paragraph boundary $p^*$ to $p$ (to avoid mid-sentence injection)
  3. Construct injected document:

$$D(H, n, d, L) = H[0:p^_] | n | H[p^_:L]$$

where $|$ denotes string concatenation and $H[a:b]$ is the token slice from position $a$ to $b$.

  1. The final document is truncated or padded to exactly $L$ tokens

Boundary Enforcement: Injection always occurs at paragraph boundaries (double newline \n\n) to avoid syntactically malformed sentences that would make needle location artificially obvious.

3. Task Definitions

3.1 S-RT: Single-Needle Retrieval

Definition: A single synthetic fact $n$ is inserted at depth $d$ in a haystack of length $L$. The model is queried to retrieve the specific value.

Experimental Grid: $$\text{Grid} = {(L_i, d_j) : L_i \in \mathcal{L}, d_j \in \mathcal{D}}$$

where $\mathcal{L}$ is a set of target context lengths and $\mathcal{D}$ is a set of depth percentages.

Needle Template:

The [attribute] of [fictional_entity] is [synthetic_value].

Entity names are drawn from a synthetic vocabulary of obviously fictional planet names, chemical compounds, and proper nouns (e.g., "Zyranthex-7", "Project Heliodrome") to prevent model knowledge contamination.

Query: "What is the [attribute] of [fictional_entity]? Provide only the value."

Scoring: $$s_{\text{S-RT}}(r, n) = \begin{cases} 1.0 & \text{if normalize}(v_n) \in \text{normalize}(r) \ 0.0 & \text{otherwise} \end{cases}$$

where $v_n$ is the ground-truth value in needle $n$ and normalize strips whitespace and lowercases.

Output: 2D heatmap where cell $(L_i, d_j)$ shows $s_{ij}$.

Aggregate Score: $$\text{S-RT Score} = \frac{1}{|\mathcal{L}| \cdot |\mathcal{D}|} \sum_{i,j} s_{ij}$$

3.2 M-RT: Multi-Needle Retrieval

Definition: $N$ synthetic facts ${n_1, ..., n_N}$ are inserted at depths ${d_1, ..., d_N}$. The model must retrieve all $N$ values.

Depth Distribution Strategies:

Strategy Formula Depth axis
Uniform $d_k = 0.05 + \frac{0.9(k-1)}{N-1}$ for $k = 1,...,N$ Collapsed to single value†
Centered Needles span $[\text{base_depth} - \delta, \text{base_depth} + \delta]$ Swept (base depth varies)
Random $d_k \sim \text{Uniform}(0.05, 0.95)$, sorted Swept (new sample each cell)
Bookends $d_1 = 0.05$, $d_N = 0.95$, interior points uniform Collapsed to single value†

† Depth-sweep deduplication: For uniform and bookends, needle placement is identical regardless of which depth_percent value is the "base". Running the full depth grid would repeat the same test. HaystackBench therefore collapses the depth axis to a single representative value (0.5) when num_needles > 1 and the distribution is uniform or bookends. This reduces cell count by a factor equal to len(depth_percents) for these configurations. The centered and random strategies are unaffected — centered uses base_depth as the cluster centre (so the depth sweep is meaningful), and random produces a different layout each call.

Scoring (Partial Credit): $$s_{\text{M-RT}}(r, {n_1,...,n_N}) = \frac{1}{N} \sum_{k=1}^{N} s_{\text{S-RT}}(r, n_k)$$

Individual needle scores: check whether value $v_{n_k}$ appears in the response $r$.

Aggregate: $$\text{M-RT Score}(N) = \frac{1}{|\mathcal{L}| \cdot |\mathcal{D}|} \sum_{i,j} s_{ij}(N)$$

Reported as a function of $N$ to show retrieval degradation with needle count.

3.3 M-RS: Multi-Needle Reasoning

Definition: $N$ needles contain numeric or logical facts that must be synthesized to answer a reasoning question. The answer cannot be retrieved from any single needle.

Needle Generation (Numeric):

For $N$ needles with values ${v_1, ..., v_N}$ where $v_k \sim \text{Uniform}(1, 999)$:

The [attribute] of [entity_k] is [v_k].

Reasoning Types:

Type Query Ground Truth
Sum "What is the total [attribute] across all entities?" $\sum_k v_k$
Max "Which entity has the highest [attribute]?" $\arg\max_k v_k$
Mean "What is the average [attribute]?" $\frac{1}{N}\sum_k v_k$
Conditional "What is the [attr] of entities where [condition]?" Filtered subset
Chain "Entity A gives half its value to Entity B. What does B have?" $v_B + v_A/2$

Scoring: $$s_{\text{M-RS}}(r, \text{gt}) = \begin{cases} 1.0 & \text{if parse_numeric}(r) = \text{gt} \pm \epsilon \ s_{\text{LLM-judge}}(r, \text{gt}) & \text{for non-numeric} \ 0.0 & \text{otherwise} \end{cases}$$

where $\epsilon = 0.01 \cdot |\text{gt}|$ (1% tolerance for floating point).

3.4 ATC: Ancestral Trace Challenge

Definition: The document contains only relational facts (no haystack filler). The model must perform multi-hop reasoning over a graph of relationships to answer a query.

Graph Construction:

Let $G = (V, E)$ be a directed graph where:

  • Nodes $V$ are named entities (fictional persons)
  • Edges $E$ are first-order relationships (parent-of, reports-to, precedes, etc.)

Structure Types:

Structure Description Example Query
Chain Linear sequence: $A \to B \to C \to ...$ "Who is the great-grandparent of Z?"
Binary Tree Complete binary tree of depth $k$ "Who are the siblings of Y?"
DAG Directed acyclic graph with multiple paths "Who is the common ancestor of X and Y?"

Relationship Document Format:

[Person_A] is the parent of [Person_B].
[Person_B] is the parent of [Person_C].
...

Relationships are shuffled randomly within the document to prevent trivial sequential scanning.

Hop Depth: For chain tasks, hop depth $h$ means the query requires traversing exactly $h$ edges. Tests range from $h=2$ (grandparent) to $h=10$.

Scoring: $$s_{\text{ATC}}(r, v^) = \begin{cases} 1.0 & \text{if normalize}(v^) \in \text{normalize}(r) \ 0.0 & \text{otherwise} \end{cases}$$

where $v^*$ is the unique correct entity.

Why No Haystack Filler? In ATC, all text is signal — there is no irrelevant background text. Context length is controlled by the number of relationships in the document. This tests reasoning over long documents rather than retrieval within noisy text.

3.5 Counting Task

Definition: A specific pattern (needle) appears exactly $k$ times in the document. The model must count occurrences.

Needle: Short, distinctive phrase (e.g., "The secret password is ALPHA-7").

Scoring: $$s_{\text{COUNT}}(r, k) = \begin{cases} 1.0 & \text{if parse_int}(r) = k \ \max\left(0, 1 - \frac{|parse_int}(r) - k|}{k}\right) & \text{partial credit} \end{cases}$$

3.6 Key-Value Retrieval

Definition: $K$ key-value pairs are scattered throughout the document. The model must retrieve the value for a specific key.

Document Format:

...filler...
{key_17}: {value_17}
...filler...
{key_42}: {value_42}
...

Keys are UUID-like identifiers (e.g., kv_7a3f2b) to prevent semantic shortcuts.

Scoring: Exact match on the value string.

This task directly measures attention capacity — as $K$ grows and $L$ increases, can the model find the right key-value pair?

3.7 Conflicting Needles

Definition: Two contradictory facts are inserted at different depths. The model's answer reveals which it "believes."

Example:

  • Needle A (at depth $d_A$): "The boiling point of Xenarium is 412 degrees."
  • Needle B (at depth $d_B$): "The boiling point of Xenarium is 891 degrees."
  • Query: "What is the boiling point of Xenarium?"

Scoring:

  • Score = 0 or 1 depending on which answer the model gives
  • Recorded as: chose_first (primacy) or chose_last (recency) or chose_neither (refusal)

Bias Measurement: $$\text{Primacy Bias Rate} = \frac{\sum \mathbb{1}[\text{chose_first}]}{|\text{total cells}|}$$ $$\text{Recency Bias Rate} = \frac{\sum \mathbb{1}[\text{chose_last}]}{|\text{total cells}|}$$

This reveals fundamental positional biases in the model's attention mechanism.

3.8 Distractor Needles

Definition: The correct needle is surrounded by semantically similar but incorrect "distractor" needles. Tests retrieval precision.

Example:

  • Correct: "The mass of planet Voranthix-9 is 7.42 stellar units."
  • Distractor 1: "The mass of planet Voranthix-8 is 3.17 stellar units."
  • Distractor 2: "The mass of planet Voranthix-10 is 9.61 stellar units."
  • Query: "What is the mass of planet Voranthix-9?"

Scoring: Exact match — must retrieve the value for the specific entity queried.

4. Needle Generation

4.1 Synthetic Abstract Needles

Needles use a three-part template that avoids real-world knowledge:

The [attribute] of [entity] is [value].

Entity Vocabulary: Generated by combining:

  • Syllable patterns: (2-4 syllables from a phoneme inventory)
  • Disambiguators: numeric suffixes, Greek letters, cardinal directions

Examples: Zyranthex-7, Project Heliodrome, Compound Delta-Krylos, Station Omicron-IV

Attribute Vocabulary: Domain-specific but unfamiliar:

  • orbital period, resonance frequency, thermal coefficient, migration index

Value Vocabulary:

  • Numeric: integer or float in a specified range
  • String: short alphanumeric codes (e.g., QR-7749, BETA-PRIME)

Uniqueness Guarantee: For M-RT runs, all $N$ entity-attribute pairs in a batch are unique to prevent ambiguous retrieval.

4.2 Template-Based Needles

Users provide a Jinja2 template:

The secret passcode for {{ entity }} is {{ code }}.

With variable generators:

entity:
  type: wordlist
  values: [Vault A, Chamber B, Section C]
code:
  type: random_hex
  length: 8

4.3 Custom Needle Library

Users can define their own needle/expected-answer pairs in the Settings UI. These are stored in a persistent library and can be selected per-experiment from the wizard.

When custom needles are selected:

  • The full (needle_text, expected_answer, question) tuples are embedded into the experiment config at creation time, making the experiment self-contained
  • If num_needles > 1, the pool is cycled cyclically across cells (e.g., 2 custom needles used for a 3-needle cell: needle 0, needle 1, needle 0)
  • Each cell's starting position in the pool is seeded from (experiment_id, model, trial), keeping the needle assignment consistent across (context_length × depth) for a given trial

Custom needles are suited for domain-specific evaluation (e.g., medical codes, legal citations, product IDs) where synthetic abstract needles may not reflect real retrieval difficulty.

4.4 Relational Needles (ATC)

Generated algorithmically from a graph structure:

for (parent, child) in G.edges():
    yield f"{parent} is the parent of {child}."

Entity names are generated to be:

  1. Clearly human names (to suggest a social/kinship graph)
  2. Phonetically distinct (to avoid confusion between similar names)
  3. From a closed set for a given experiment (no external knowledge needed)

5. Haystack Construction

5.1 Paul Graham Essays (Standard)

The original Kamradt NIAH uses a corpus of Paul Graham essays as the background "haystack." This text:

  • Is freely available
  • Has uniform style (minimal variation in prose register)
  • Contains rich vocabulary that could plausibly contain any synthetic fact
  • Is well-studied as a benchmark baseline

Source: Public HTML from paulgraham.com, concatenated and cleaned.

Padding Strategy: When the required length exceeds available text, the corpus is repeated (with a separator) until the target length is reached.

5.2 Wikipedia Articles

Random Wikipedia articles provide domain-diverse haystacks. For reproducibility, experiments should specify:

  • Language: en
  • Random seed: ensures same articles are fetched across runs
  • Article count: number of articles concatenated

5.3 arXiv Abstracts

Computer science and ML paper abstracts create a technical prose haystack appropriate for ML benchmarking.

5.4 Synthetic Haystacks

For complete control, synthetic paragraphs can be generated. These are useful for:

  • Domain-specific benchmarking (legal, medical)
  • Ablation studies on haystack type

5.5 Token Length Calculation

All token counts use tiktoken with the cl100k_base vocabulary (OpenAI's standard) as a universal reference. This is an approximation for non-OpenAI models but provides consistent cross-provider comparison.

For billing-accurate estimates, providers' native tokenizers are invoked when available.

6. Scoring Methodology

6.1 Exact Match

normalize(v) = v.strip().lower()
score = 1.0 if normalize(expected) in normalize(response) else 0.0

Used for: S-RT, M-RT, KV retrieval, ATC

6.2 Substring Match

The expected value appears as a substring of the response (after normalization). More lenient than exact match.

6.3 Semantic Similarity

Using sentence-transformers (all-MiniLM-L6-v2 by default): $$s_{\text{sem}}(r, e) = \cos\left(\phi(r), \phi(e)\right)$$

where $\phi$ is the sentence embedding function.

Threshold: $s_{\text{sem}} \geq 0.8$ → correct.

6.4 LLM Judge

A separate model (default: cheapest available, e.g., claude-3-5-haiku) evaluates correctness:

Judge Prompt:

You are a strict fact-checking judge.

Ground truth answer: {expected}
Model response: {response}

Does the model's response correctly contain the ground truth answer?
Answer with only "YES" or "NO" followed by a one-sentence explanation.

Parsed: "YES" → score = 1.0, "NO" → score = 0.0.

6.5 Numeric Match

parse_numeric(response) → float
score = 1.0 if |parsed - expected| / max(|expected|, 1) < 0.01 else 0.0

6.6 Scoring Method Selection

Task Default Scorer Notes
S-RT auto Auto-selects: numeric (1% relative tolerance) for float/int values, substring otherwise. Handles model rounding correctly.
M-RT substring (per needle) Applied to each needle independently
M-RS numeric → LLM judge Numeric first, fall back to LLM judge
ATC exact Entity names are unambiguous
Counting numeric Must parse integer from response
KV exact Values are designed to be exact
Conflicting categorical Parse which value was chosen
Distractor exact Must get precisely the right entity's value

The auto method (used by S-RT) calls _parse_numeric() on the expected answer; if it parses as a float, the response is scored numerically with 1% relative tolerance. This correctly handles cases where a model responds with a rounded value (e.g., expected 732.57, response 733) or adds units (732.57 M⁻¹).

7. Known Biases & Limitations

7.1 Positional Biases

LLMs exhibit well-documented positional biases:

  • Lost in the Middle (Liu et al., 2023): Models perform worse when relevant information is in the middle of a long context
  • Recency Bias: Models tend to preferentially recall information from the end of the context
  • Primacy Bias: Models sometimes preferentially recall the beginning

HaystackBench's heatmaps directly visualize these biases.

7.2 Haystack Contamination

The Paul Graham haystack is public text that models may have seen during training. This could create "familiar text" effects where known passages make retrieval easier or harder. Using synthetic haystacks eliminates this concern.

7.3 Tokenizer Mismatch

Using tiktoken as a universal token counter introduces slight inaccuracies for non-OpenAI models (especially for non-English text). The context_length axis should be interpreted as "approximate."

7.4 Needle Memorization

If synthetic needle templates are published, future models trained on internet text could memorize them. Users running long-term evaluations should rotate templates.

7.5 Single-Trial Variance

With trials_per_cell=1, variance from model stochasticity (even at temperature=0, many providers use non-zero temperature by default) is not captured. For publication, use trials_per_cell≥3.

7.6 Instruction Following Conflation

If a model fails a retrieval task, it may be due to:

  1. Failing to retrieve the needle (true context failure)
  2. Formatting errors (retrieved correctly but in wrong format)
  3. Instruction non-compliance

LLM judge scoring mitigates case 2 and 3 but adds cost.

8. Interpreting Results

8.1 Heatmap Reading Guide

Context Length (tokens) →
4K     8K     16K    32K    64K    128K
┌──────┬──────┬──────┬──────┬──────┬──────┐  0% (top)
│ 1.00 │ 1.00 │ 1.00 │ 0.90 │ 0.80 │ 0.60 │
├──────┼──────┼──────┼──────┼──────┼──────┤  20%
│ 1.00 │ 1.00 │ 0.90 │ 0.70 │ 0.50 │ 0.30 │
├──────┼──────┼──────┼──────┼──────┼──────┤  40%
│ 1.00 │ 0.90 │ 0.70 │ 0.50 │ 0.30 │ 0.10 │  ← "Lost in the Middle"
├──────┼──────┼──────┼──────┼──────┼──────┤  60%
│ 1.00 │ 1.00 │ 0.90 │ 0.70 │ 0.50 │ 0.30 │
├──────┼──────┼──────┼──────┼──────┼──────┤  80%
│ 1.00 │ 1.00 │ 1.00 │ 0.90 │ 0.80 │ 0.70 │
└──────┴──────┴──────┴──────┴──────┴──────┘  100% (bottom)

Patterns to look for:

Pattern Visual signature Interpretation
"Lost in the Middle" Dark horizontal band in center Model struggles with mid-context information
"Context Cliff" Green columns → red columns at some length Hard cutoff in effective context use
"End Advantage" Bottom rows brighter than top Recency bias
"Diagonal Fade" Score decreases moving right-down Combined depth and length degradation
"Perfect Square" All cells green Model handles task at all settings

8.2 Aggregate Score Interpretation

Score Interpretation
0.95–1.00 Excellent: effectively uses full context
0.80–0.95 Good: minor degradation at extreme lengths/depths
0.60–0.80 Fair: noticeable degradation; specific weaknesses exist
0.40–0.60 Poor: significant context limitations
< 0.40 Failing: claimed context length not functionally available

8.3 Multi-Task Radar Chart

The radar chart shows performance across all task types simultaneously. "Balanced" models show a roughly circular profile. Models optimized for one task type may show a "spike" pattern.

9. Comparison with Existing Benchmarks

9.1 Kamradt NIAH (2023)

Similarities: Same basic S-RT concept; Paul Graham haystack; depth × context grid.

Differences:

  • Kamradt: ad-hoc script, no M-RT/M-RS/ATC, limited provider support
  • HaystackBench: full framework, 8 task types, web UI, comprehensive scoring, export formats

9.2 NeedleBench (BAAI, 2024)

Similarities: Multi-needle variants; ATC; systematic evaluation.

Differences:

  • NeedleBench: research codebase, no UI, limited provider abstraction
  • HaystackBench: production-grade tool, extensible provider system, web UI, CLI

9.3 RULER (Hsieh et al., 2024)

RULER includes: NIAH variants, variable tracking, common/rare word aggregation, and question answering.

Differences:

  • RULER: academic research tool focused on specific failure modes
  • HaystackBench: practitioner-focused, configurable, multi-provider, with UI

9.4 LongBench (Bai et al., 2023)

LongBench tests real-world long-document tasks (summarization, QA, etc.).

Differences: HaystackBench tests synthetic controlled tasks to isolate context utilization from other capabilities. The two tools are complementary.

10. Reproducibility Checklist

For publication-quality results, ensure:

  • trials_per_cell ≥ 3 to capture variance
  • temperature=0.0 for deterministic responses (where supported)
  • Record exact model version (not just model name)
  • Record exact haystack source and version
  • Record exact needle templates used
  • Export full JSON results (not just summary scores)
  • Record haystackbench version: haystackbench --version
  • Include the experiment YAML config in supplementary materials

11. Citation

If you use HaystackBench in research, please cite:

@software{haystackbench2025,
  title  = {HaystackBench: A Comprehensive NIAH Evaluation Framework for Large Language Models},
  year   = {2025},
  url    = {https://github.com/marmutapp/needlehaystack},
  note   = {Open-source software}
}

References

  1. Kamradt, G. (2023). Needle In A Haystack - Pressure Testing LLMs. GitHub. https://github.com/gkamradt/LLMTest_NeedleInAHaystack

  2. Li, M., et al. (2024). NeedleBench: Can LLMs Do Retrieval and Reasoning in 1 Million Context Window? BAAI. arXiv:2407.11963.

  3. Hsieh, C., et al. (2024). RULER: What's the Real Context Size of Your LLM? arXiv:2404.06654.

  4. Bai, Y., et al. (2023). LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding. arXiv:2308.14508.

  5. Liu, N., et al. (2023). Lost in the Middle: How Language Models Use Long Contexts. arXiv:2307.03172.