The AI Blind Spot: Why Language Models Confuse Elixir Lists with Arrays

Abstract

Large Language Models (LLMs) have become ubiquitous tools for software development, generating code and explaining algorithms at scale. Yet they harbor a systematic blind spot: when analyzing Elixir code, they consistently treat [] as an array, applying O(1) complexity assumptions that are flatly wrong for a linked list. This misconception is not a minor pedantic quibble—it produces incorrect complexity analyses, misleading performance expectations, and subtly broken code. This article dissects the error, explains the actual memory layout and performance characteristics of Elixir's fundamental data structures, and argues that the fix is not merely technical but conceptual.

Introduction

Imagine asking an AI to optimize a dynamic programming solution in Elixir. It confidently responds with a nested loop, using Enum.at/2 and List.replace_at/3 on a list, and declares the time complexity to be O(n × k). The code compiles. The tests pass on small inputs. But hidden beneath the surface, the algorithm is actually O(n × k²)—a quadratic blowup that will time out on any realistic input.

This scenario is not hypothetical. It is a recurring, reproducible failure mode. The AI has confused a linked list with an array, and that confusion has cascaded into a flawed algorithm and a wrong complexity analysis.

The root cause is simple: in Elixir, [] is not an array. It is a singly linked list. The closest thing to an array in Elixir is the tuple ({}). This distinction is fundamental to writing performant Elixir code, yet it is precisely the distinction that language models, trained predominantly on imperative languages like Python and Java, consistently miss.

The Error, Demonstrated

Let us make the failure concrete. An AI, asked to implement a bottom-up dynamic programming solution in Elixir, might produce the following:

# AI-generated "O(n × k)" solution — actually O(n × k²)
def build_dp(n, k) do
  initial_dp = List.duplicate(0, k + 1) |> List.replace_at(0, 1)

  Enum.reduce(1..n, initial_dp, fn i, dp ->
    max_j = min(i, k)
    1..max_j
    |> Enum.reduce(dp, fn j, acc ->
      valor = (j * Enum.at(acc, j) + Enum.at(acc, j - 1)) |> rem(@mod)
      List.replace_at(acc, j, valor)
    end)
  end)
  |> Enum.at(k)
end

The AI's reasoning is transparent: it has seen dynamic programming solutions in Python or C++ that use a one-dimensional array dp[j], and it has mechanically translated dp[j] into Enum.at(dp, j) and dp[j] = value into List.replace_at(dp, j, value). It assumes these operations are O(1), just as they are for an array.

They are not.

The Reality: Lists Are Linked, Tuples Are Contiguous

Elixir's official documentation is unambiguous:

Lists are implemented as linked lists (where each item in the list points to the next item) while tuples are stored contiguously in memory. This means that accessing a tuple element is very fast (constant time) and can be achieved using the elem function.

Accessing an element in a tuple is constant $O(1)$ complexity because the size of the tuple is already known. Accessing an element in a list is $O(n)$ complexity where n is the index of the element we need to access.

In a linked list, each element is stored in a "cons cell" containing the value and a pointer to the next element. To reach index j, the runtime must follow j pointers, yielding O(j) access time. Updating an element is even worse: List.replace_at/3 must traverse to the index and then reconstruct the list from that point forward, also O(j).

A tuple, by contrast, stores its elements contiguously in memory, like a C array. elem/2 is a constant-time operation, and put_elem/3 produces a shallow copy of the entire tuple—O(k) for a tuple of size k, but with a small constant factor.

The performance implications are stark. A benchmark in the Elixir curriculum demonstrates that accessing elements in a tuple is orders of magnitude faster than accessing them in a list, and the gap widens as the index grows.

The Correct Implementation: Tuples as Arrays

The efficient Elixir solution uses tuples, not lists:

# Correct O(n × k) solution using tuples
def build_dp(n, k) do
  initial_dp =
    0..k
    |> Enum.map(fn j -> if j == 0, do: 1, else: 0 end)
    |> List.to_tuple()

  final_dp =
    Enum.reduce(1..n, initial_dp, fn i, dp ->
      max_j = min(i, k)
      0..k
      |> Enum.map(fn j ->
        cond do
          j == 0 -> 0
          j > max_j -> 0
          true -> (j * elem(dp, j) + elem(dp, j - 1)) |> rem(@mod)
        end
      end)
      |> List.to_tuple()
    end)

  elem(final_dp, k)
end

The key insight is that reconstructing the entire tuple in a single Enum.map pass is O(k), not O(k²). The AI's mistake was to perform k individual put_elem/3 operations, each O(k), resulting in O(k²) per row.

Why the AI Gets It Wrong

The error is not random. It stems from three compounding factors:

Training data bias. The overwhelming majority of algorithmic code on the internet is written in Python, Java, C++, or JavaScript—languages where [] is an array with O(1) indexed access. An LLM trained on this corpus has learned a strong prior: "square brackets mean array." When it encounters Elixir syntax, it applies this prior without checking the underlying semantics.

Superficial syntactic similarity. Elixir's [] syntax looks identical to Python's list syntax. The AI sees dp = [0, 0, 0] and assumes it behaves like a Python list (which is itself a dynamic array). It does not "know" that Elixir's [] is a cons-cell linked list unless explicitly prompted.

Lack of runtime feedback. An AI generating code does not execute it. It cannot observe the quadratic slowdown. The error is silent, and the AI has no mechanism to detect it.

This is a specific instance of a broader problem: LLMs are pattern matchers, not semantic reasoners. They excel at generating code that looks correct, but they do not understand the execution model of the language they are generating. Elixir's functional, immutable, BEAM-based runtime is sufficiently different from the imperative mainstream that these semantic gaps become frequent and consequential.

Beyond Lists and Tuples: A Broader Pattern

The list-vs-array confusion is the most common instance of this failure mode, but it is not the only one. Similar AI errors in Elixir include:

• Treating String operations as O(1): Elixir strings are UTF-8 binaries, and String.at/2 is O(n), not O(1). An AI optimizing a string algorithm may naively use String.at in a loop, producing quadratic behavior.
• Assuming Enum.length/1 is O(1): It is O(n) for lists. An AI may call length/1 inside a loop, unaware of the traversal cost.
• Confusing maps with hash tables: Elixir maps have O(log n) access, not O(1). An AI familiar with Python dicts may assume constant-time lookups.

The common thread is that the AI is applying performance models from imperative languages to a functional runtime. Elixir's data structures are persistent, immutable, and structurally shared—properties that fundamentally alter their complexity characteristics.

The Cost of the Error

Why does this matter? Because incorrect complexity analysis is not a cosmetic issue. It leads to:

1. Algorithms that pass small tests but fail at scale. The O(n × k²) DP solution will work for n=100, but time out for n=1000.
2. Misleading interview preparation. Candidates who trust AI-generated analyses will walk into interviews with wrong mental models.
3. Erosion of trust. When an AI confidently declares an algorithm to be O(n × k) and it is actually O(n × k²), users lose confidence in the tool's reliability.

The most dangerous aspect is that the error is invisible in code review. The syntax is correct. The logic is correct. Only the performance model is wrong—and performance models are rarely scrutinized in pull requests.

The Fix: Semantic Awareness, Not Just Syntax

The solution is not to abandon AI tools, but to demand that they reason about the execution model of the target language, not just its syntax. For Elixir, this means:

1. Explicitly stating the data structure's semantics. An AI should know that [] is a linked list and {} is a tuple, and that this distinction matters for complexity.
2. Verifying complexity claims against the language's actual implementation. When an AI declares O(1) access, it should be able to justify it by pointing to the underlying memory model.
3. Preferring tuple-based DP in Elixir. When an algorithm requires indexed access and updates, tuples are almost always the right choice.

For human developers, the lesson is equally important: never assume that [] means the same thing in every language. In Elixir, it means linked list. In Python, it means dynamic array. In JavaScript, it means dynamic array. The syntax is universal; the semantics are not.

Conclusion

The AI's confusion between Elixir lists and arrays is a microcosm of a larger challenge in AI-assisted programming: syntactic competence does not imply semantic understanding. Language models can generate Elixir code that compiles and passes tests, yet rests on a fundamentally flawed model of how the language executes.

For Elixir specifically, the fix is clear: lists are linked lists; tuples are the closest thing to arrays. Any AI analysis that treats Enum.at/2 as O(1) or List.replace_at/3 as cheap is wrong, and the resulting complexity claims are unreliable.

As AI tools become more integrated into development workflows, the burden shifts to developers to critically evaluate performance claims, especially in languages with non-mainstream execution models. Elixir, with its immutable data structures and BEAM runtime, is precisely such a language. The list-vs-array error is not an edge case—it is a wake-up call.