📊 statistics

TCARD: Nearly Balanced Two-Level Designs with Treatment Cardinality Constraints with an Application to LLM Prompt Engineering

This paper introduces TCARD, a framework for constructing nearly balanced two-level experimental designs under treatment cardinality constraints by proposing a model-free Balanced Concurrence Deviation criterion and an efficient coordinate-exchange algorithm to optimize designs for applications like LLM prompt engineering.

Original authors: Kexin Xie, Ryan Lekivetz, Xinwei Deng

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kexin Xie, Ryan Lekivetz, Xinwei Deng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create the perfect new dish. You have a pantry full of 15 different ingredients (factors), but your recipe card only has space for exactly 3 ingredients per dish (the Treatment Cardinality Constraint). You want to test as many combinations as possible to figure out which ingredients make the food taste amazing and which ones ruin it.

The problem? If you just pick random combinations, you might end up testing "Salt, Salt, Salt" three times and never testing "Salt, Pepper, Basil." Or, you might test "Salt and Pepper" together so often that you can't tell if the good taste comes from the salt, the pepper, or the magic of them being together.

This paper, titled "TCARD," is about creating a smart, mathematical recipe for these experiments. It ensures that every ingredient gets a fair turn in the spotlight and that every pair of ingredients gets tested together just the right amount of times.

Here is a breakdown of their approach using simple analogies:

1. The Problem: The "Three-Ingredient" Rule

In many real-world tests—like tuning a computer program, testing drug combinations, or even writing prompts for an AI (like the one used in the paper)—you can't use everything at once.

The Constraint: You must pick exactly $k$ items out of $p$ available options for every single test run.
The Risk: If you aren't careful, your data becomes messy. You might over-test some ingredients and under-test others, making it impossible to know what actually works.

2. The Solution: "Nearly Balanced" Designs

The authors realized that the perfect mathematical solution (where every ingredient is used exactly the same number of times and every pair meets exactly the same number of times) often doesn't exist for real-world numbers. It's like trying to divide 7 cookies among 3 friends perfectly evenly—you can't do it without breaking a cookie.

So, they invented "Nearly Balanced" designs.

The Analogy: Imagine you are seating guests at a round table. You want everyone to sit next to every other guest exactly once. If you can't do that perfectly, you aim for a "nearly balanced" seating where everyone sits next to everyone else almost the same number of times.
The Goal: Minimize the "clumping" (some pairs meeting too often) and the "loneliness" (some ingredients never meeting).

3. The New Tool: The "Balanced Concurrence Deviation" (BCD) Score

To build these designs, the authors created a scoring system called $\Phi_{BCD}$ . Think of this as a "Fairness Meter" for your experiment.

Two Dials: The meter has two dials.
1. Replication Balance: Is every ingredient used roughly the same number of times?
2. Concurrence Balance: Do every pair of ingredients meet roughly the same number of times?
The Magic: The authors proved that if you minimize this score, you automatically get a design that is statistically powerful. It's like tuning a radio to the clearest station; once you hit the right spot, the static (noise) disappears, and the signal (truth) comes through clearly.

4. The Algorithm: The "Swap" Strategy

How do you find this perfect design? You can't just guess. The authors built a computer algorithm (a Coordinate-Exchange method) that works like a game of musical chairs.

The Process: It starts with a random list of 3-ingredient combinations. Then, it looks at one row (one test) and asks, "If I swap Ingredient A for Ingredient B here, does my Fairness Meter improve?"
Speed: It does this incredibly fast, swapping ingredients around until it finds the most balanced arrangement possible.

5. The "Secret Sauce": Tuning the Weights

The Fairness Meter has two dials. Sometimes you care more about making sure every ingredient is used equally (Replication). Sometimes you care more about how often pairs meet (Concurrence).

The Innovation: Instead of guessing which dial to turn, the authors suggest a simulation-based tuning. Before you run the real experiment, you run a "practice run" on a computer. You pretend to be the AI or the scientist, see what kind of results you want to find, and then adjust the dials to match that goal.
Why it matters: This ensures the experiment is built specifically to answer the question you actually care about, rather than just being "mathematically pretty."

6. The Real-World Test: The AI Chef

To prove it works, the authors tested this on Large Language Models (LLMs)—the brains behind chatbots like the one you are talking to.

The Setup: They wanted to figure out which "prompt components" (like "Think step-by-step" or "Act as an expert") actually help the AI solve math problems. They had 15 possible components but could only use 3 at a time.
The Result:
- The TCARD method (the smart, balanced recipe) found the best ingredients and identified which ones hurt the AI's performance.
- Random recipes (just guessing combinations) or greedy recipes (trying to be simple) failed. They either couldn't tell the difference between good and bad ingredients or gave misleading results.
- Specifically, the TCARD method correctly identified that "Acting as a mathematician" helped, while "Using algebraic formulas" actually confused the AI on these specific math problems.

Summary

This paper gives us a new, smarter way to run experiments when we are limited on how many things we can test at once.

Old way: Guess and check, or use rigid rules that don't fit real life.
New way (TCARD): Use a "Fairness Meter" to balance the experiment, swap ingredients around until it's perfect, and tune the settings based on what you hope to learn.

It's the difference between throwing darts blindfolded and using a laser-guided system to hit the bullseye, ensuring that every piece of data you collect actually tells you something true.

Technical Summary: TCARD: Nearly Balanced Two-Level Designs with Treatment Cardinality Constraints

Problem Statement
Modern experimental design frequently encounters the treatment cardinality constraint (TCARD), where each experimental run is restricted to activating exactly $k$ factors out of $p$ available factors. This constraint arises in diverse fields including sensor scheduling, feature-flag experiments, high-throughput drug screening, and, increasingly, the engineering of prompts for Large Language Models (LLMs). Under TCARD, the design matrix $X \in \{0, 1\}^{n \times p}$ has fixed row sums equal to $k$ .

This constraint creates significant statistical and algebraic challenges:

Structural Singularity: Fixed row sums induce linear dependencies among columns, rendering the information matrix singular or nearly singular after intercept removal.
Infeasibility of Classical Designs: Full or fractional factorial designs are impossible. While Balanced Incomplete Block Designs (BIBDs) offer a natural reference for balancing factor replications and pairwise co-occurrences, exact BIBDs do not exist for many practical $(n, p, k)$ combinations.
Lack of Optimality Criteria: Existing criteria (e.g., distance-based maximin, standard $A/D/E$ -optimality) were not designed for row-sum constraints. They often fail to control the specific structural quantities governing projection quality under TCARD: factor replication balance and pairwise concurrence balance. Furthermore, existing compound criteria lack principled guidance on how to weight these competing objectives relative to downstream tasks.

Methodology
The paper proposes a unified framework for constructing and analyzing two-level TCARDs, organized around a "counts-only" perspective.

Algebraic Foundations and "Nearly Balanced" Definition:
- The authors establish a correspondence between TCARDs and BIBDs, proving that a TCARD is fully balanced if and only if its support structure forms a BIBD.
- Since exact BIBDs are often unavailable, they formalize the concept of nearly balanced TCARDs. A design is nearly balanced if:
  - (NB1) Factor replications $r_j$ differ by at most one (i.e., $r_j \in \{\lfloor \bar{r} \rfloor, \lceil \bar{r} \rceil\}$ ).
  - (NB2) Pairwise concurrences $\lambda_{j\ell}$ are as uniform as arithmetic permits given the replication levels.
- Theoretical results (Theorems 1 and 2) show that nearly balanced TCARDs minimize the first two components of the Generalized Word-Length Pattern ( $B_1$ and $B_2$ ), which measure projection imbalances.
The Balanced Concurrence Deviation ( $\Phi_{BCD}$ ) Criterion:
- To construct designs without solving intractable integer feasibility problems, the authors introduce a model-free, real-valued objective function:
  $\Phi_{BCD}(X) = w_1 \frac{V_1(X)}{p} + w_2 \frac{V_2(X)}{\binom{p}{2}}$
  where $V_1$ is the squared deviation of replications from the mean, and $V_2$ is the squared deviation of pairwise concurrences from the mean.
- Statistical Justification: The paper proves that minimizing $\Phi_{BCD}$ $Φ_{B C D}$ aligns with several classical optimality principles:
  - It satisfies the (M, S)-optimality principle (maximizing total information, then minimizing eigenvalue spread) under main-effects models.
  - It is algebraically equivalent to the centered $UE(s^2)$ criterion (Jones and Majumdar, 2014) under specific weight conditions.
  - It provides a perturbation bound for Bayesian D-optimality, linking the counts-based penalty to the efficiency gap relative to an ideal balanced design.
Algorithmic Construction:
- A Coordinate-Exchange (CE) algorithm is developed that respects the row-sum constraint by performing within-row swaps (exchanging an active factor for an inactive one).
- The algorithm utilizes efficient $O(k)$ incremental updates to evaluate changes in $\Phi_{BCD}$ , making it scalable.
- Simulation-Based Weight Tuning: Recognizing that the weights $(w_1, w_2)$ control the trade-off between replication and concurrence balance, the authors propose an offline tuning procedure. Using a simulation plan that mimics the intended downstream task (e.g., sparse subspace selection), the weight $w_1$ is calibrated to maximize a performance metric (e.g., F1 score) before any real data is collected.

Key Results

Theoretical: The paper establishes that nearly balanced TCARDs are optimal for minimizing low-order projection imbalances ( $B_1, B_2$ ) and provides necessary conditions for their existence via graph-theoretic degree sequences.
Numerical Simulation: Across a range of problem sizes ( $p \in \{20, \dots, 80\}$ $p \in {20, \dots, 80}$ ) and constraint strengths ( $k/p \in \{0.1, 0.25, 0.5\}$ $k / p \in {0.1, 0.25, 0.5}$ ), the proposed $\Phi_{BCD}$ $Φ_{B C D}$ criterion (with default weights $w_1=w_2=1$ $w_{1} = w_{2} = 1$ ) consistently outperforms or matches existing alternatives (including $UE(s^2)$ $U E (s^{2})$ , distance-based criteria, and greedy heuristics) in terms of:
- Balance: Achieving near-perfect replication balance and superior concurrence regularity.
- Projection Quality: Yielding higher average log-determinants of projected information matrices.
- Downstream Performance: In sparse screening simulations, designs optimized with $\Phi_{BCD}$ (especially when weights are tuned to the target sparsity level $q$ ) achieve higher F1 scores, precision, and recall compared to untuned or single-component criteria.
Case Study (LLM Prompt Engineering):
- Applied to screening 15 prompt components for an Llama 3.1 8B model on the GSM8K math reasoning benchmark with a budget of 21 runs ( $k=3$ ).
- Findings: The tuned $\Phi_{BCD}$ designs (calibrated for different assumed sparsity levels $q \in \{3, 4, 5\}$ ) identified significantly more robust main effects (e.g., "Algebra" and "DrawTable" as harmful; "StepByStep" and "SubProblems" as helpful) compared to competitors.
- Validation: On a held-out test set, only the tuned $\Phi_{BCD}$ designs successfully predicted both harmful components (lowering accuracy when added) and helpful components (raising accuracy). Competing methods, including the untuned default and distance-based criteria, failed to identify helpful components, often resulting in negative or null gains.

Significance and Claims
The paper claims to provide the first comprehensive framework for nearly balanced designs under strict treatment cardinality constraints. Its significance lies in three areas:

Bridging Theory and Practice: It extends the classical theory of nearly balanced block designs (Cheng and Wu, 1981) to the TCARD setting, providing existence conditions and optimality guarantees for a class of designs previously lacking a constructive theory.
Model-Free Optimality: It introduces $\Phi_{BCD}$ , a criterion that is computationally efficient, model-free, yet rigorously connected to classical statistical optimality principles (M-S, $UE(s^2)$ , Bayesian D).
Task-Aware Calibration: It addresses the gap in compound design criteria by proposing a simulation-based tuning procedure. This allows the design criterion to be aligned with specific downstream inferential goals (e.g., variable selection vs. prediction) without requiring prior knowledge of the response surface.

The authors modestly note that while the framework handles the exact-cardinality regime effectively, it does not solve all false-positive or interaction problems inherent in screening. However, it offers a robust, task-aware foundation for constructing designs where the number of active factors is strictly bounded, a constraint increasingly common in AI and engineering applications.